程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode之數組中找兩數和為指定值

leetcode之數組中找兩數和為指定值

編輯:關於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


思路:

最直接的思路當然是兩兩嘗試,但是這樣的時間復雜度為O(n2),這樣的時間復雜度不到萬不得已還是不要接受,再嘗試思考,如果能用target減去數組中的一個數然後得到結果再到數組中搜尋,如果能找到即可,這樣的話無疑就需要一個能搜索的數據結構了,想到map,先遍歷一遍簡歷搜索庫,然後再按照以上思路進行,這樣的時間復雜度為O(n),代價是以空間換時間,這樣是不是最優解呢?以後再慢慢思考吧,反正我的這段代碼是通過了leetcode OJ的。
代碼:

class Solution {
public:
    vector twoSum(vector &numbers, int target) {
        std::map finder;
		for (int i = 0; i(val, i));
		}
		for (int i = 0; i re;
				if(finder[left]==i)
				{
				    continue;
				}
				else if (finder[left]

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved