1. Two Sum

柔光的暖阳◎ 2024-04-17 20:43 9阅读 0赞

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = \[2, 7, 11, 15\], target = 9,

Because nums\[0\] + nums\[1\] = 2 + 7 = 9,  
return \[0, 1\].

给定一个数组，寻找里面的元素，使得它们的和等于给定的target，并返回下标。

解题思路：  
本题就是3-Sum题目得简易版本，少了一层循环那种。  
解题思路：先对数组排序，然后让a从最小数开始往大找，让b从最大数往小找，再计算a+b的和，如果这个和小于target，说明需要调整a,让a更大。如果a+b大于target，说明应该调整b，让b变小才有可能使得和等于target；如果和恰好等于target，那么找到了结果。

值得注意的是，题目要求返回这些元素在原来数组的中下标，而不是排序以后的。因此我们需要做元素到其在原数组下标的映射。这个映射用struct来绑定就好啦~~~~  
时间复杂度： O ( n l o g n ) + O ( n ) O(nlogn) +O(n) O(nlogn)\+O(n)  
代码：

class Solution { 
    public:
    	struct _bind
    	{ 
    		int val;
    		int index;
    		bool operator<(const _bind &rh) const
    		{ 
    			return val < rh.val;
    		}
    	};
    	vector<int> twoSum(vector<int>& nums, int target) { 
    		vector<int> rst;
    		vector<_bind> bind;
    		for (int i = 0; i < nums.size(); i++)
    		{ 
    			bind.push_back({  nums[i], i });
    		}
    		sort(bind.begin(), bind.end());
    		int left = 0, right = nums.size()-1;
    		while (left<right)
    		{ 
    			int sum = bind[left].val + bind[right].val;
    			if (sum < target)
    			{ 
    				left++;
    			}
    			else if (sum>target)
    			{ 
    				right--;
    			}
    			else if (sum == target)
    			{ 
    				rst.push_back(bind[left].index);
    				rst.push_back(bind[right].index);
    				break;
    			}
    		}
    		return rst;
    	}
    };

结果：  
Runtime: 8 ms, faster than 92.48% of C++ online submissions for Two Sum.  
Memory Usage: 9.7 MB, less than 57.77% of C++ online submissions for Two Sum.