问题描述
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
说是给一个integer数组nums，并给一个integer的值target，让返回数组中两个元素相加等于target的索引对。
未通过的方法
我看此题的的等级是Easy，想都没想直接就来了个for嵌套，如下：
1 class Solution { 2 public: 3 vector<int> twoSum(vector<int>& nums, int target) { 4 std::vector<int> tempIndex; 5 for(int i = 0; i != nums.size(); i++) 6 { 7 for(int j = 0; j != nums.size(); j++) 8 { 9 if(((nums[i] + nums[j]) == target) && i != j) 10 { 11 tempIndex.push_back(i); 12 tempIndex.push_back(j); 13 14 return tempIndex; 15 } 16 } 17 } 18 19 return tempIndex; 20 } 21 };
可想而知，overtime，系统容忍不了O（N2）的复杂度。那就只能是想办法来降复杂度了，因此笨人笨方法，我画了个例子来看看有啥规律没（真够笨啊。。。）
图1
上图1中标有0、1、2、3的框代表数组，其数值代表了索引，而图中的两个数组是一样的，这是为了描述for嵌套方便而已。有向边表示了外层for循环指向内层for循环。而最底下的<x, y>中表示对应的索引对，举例来说就是当外层循环的i = 0时，内层循环的j分别取0、1、2、3时构成的索引对< >、<0, 1>、<0, 2>、<0, 3>，其中空的< >表示索引值不能相同。全部写开后可以看出，因为是对同一个数组进行操作，所以<x, y>与<y, x>是一致的，可以完全只取绿色部分即可，因此表现到代码里边也是十分的简单。
通过的方法
只需在内层for循环时跳过重复的索引对，也就是将j = (i + 1)即可，这样整体复杂度是不是降了？
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { std::vector<int> tempIndex; for(int i = 0; i != nums.size(); i++) { for(int j = (i + 1); j != nums.size(); j++) { if(((nums[i] + nums[j]) == target) && i != j) { tempIndex.push_back(i); tempIndex.push_back(j); return tempIndex; } } } return tempIndex; } };
原文：http://www.cnblogs.com/keikain/p/5618862.html