程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode(1) Two Sum

LeetCode(1) Two Sum

編輯:關於C++

題目:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

分析:

該題目標記為Medium,難度為中等,閱讀題目後,第一反應便是兩次遍歷數組,些許判斷便可解決。然後三下五除二寫下了代碼,信心滿滿提交:
class Solution
{
public:
    vector twoSum(vector &numbers , int target)
    {
        vector index;
        for(int i=0 ; i!=numbers.size(); i++)
        {
            for(int j=numbers.size()-1 ; j>i; j--)
                if((numbers[i]+numbers[j]) == target)
                {
                    index.push_back(i+1);
                    index.push_back(j+1);
                    break;
                }

        }//for
        return index;
    }//twoSum
};
沒錯,想嘛,堂堂LeetCode中等難度的題目,就這樣可以AC的話豈不是。。。於是,我就得到了這樣的回應: Status:

Time Limit Exceeded


再次分析:

重新審視題目,上面提供的O(n^2)的算法肯定達不到要求,到底應該用什麼方式可以避免重疊循環,思來想去還是沒有答案,最終還是只能求助百度了。當掃到一網友的分析後,恍然大悟,我們學習哈希干嘛的呀,就是因為它有著與生俱來的復雜度的優勢。 廢話不多說,下面提供AC代碼:
class Solution
{
public:
    vector twoSum(vector &numbers , int target)
    {
        vector index;
        map hashMap;
        for(unsigned int i=0 ; i這樣,算法復雜度就降到了O(n),順利AC了我的第一個LeetCode題目。
看來,自己還是水到家了,還需要繼續努力!

測試main函數:

為了方便程序測試,這兒也提供main函數的代碼,供於參考:
int main()
{
    Solution s;
    int arr[3] = {3,2,4};
    int target = 6;
    vector numbers(arr , arr+3);
    vector index;
    index = s.twoSum(numbers , target);

    cout<<"index1="<
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved