1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        // 2. 二分查找 (可过) 时间复杂度为O(N*log N)
        // vector<int> ret;
        // for (int i = 0; i < numbers.size(); i++) {
        //     int sub = target - numbers[i];
        //     int left = i + 1;
        //     int right = numbers.size();
        //     int midIndex = (left + right) / 2;
        //     while (left < right) {
        //         if (numbers[midIndex] > sub) {
        //             right = midIndex;
        //         }
        //         else if(numbers[midIndex] < sub) {
        //             left = midIndex + 1;
        //         }
        //         else {
        //      	   ret.push_back(i + 1);
        //      	   ret.push_back(midIndex + 1);
        //      	   break;
        //         }
        //      
        //         midIndex = (left + right) / 2;
        //     }
        //    if (!ret.empty())		// 结果数组中已存在数据, 表示已找到
        //       break;
        // }
        //
        // return ret;

        // 3. 双指针 (最多只遍历一边数组) 时间复杂度O(N)
        int left = 0;
        int right = numbers.size() - 1;

        vector<int> ret;

        while (left < right) {
            int addRst = numbers[left] + numbers[right];
            if (addRst < target)
                left++;
            else if (addRst > target)
                right--;
            else {
                ret.push_back(left + 1);
                ret.push_back(right + 1);
                break;
            }
        }

        return ret;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int numsSize = nums.size();

        vector<vector<int>> ret;

        // 先排序
        sort(nums.begin(), nums.end());

        for (int firstIndex = 0; firstIndex < numsSize - 2; firstIndex++) {
           	// firstIndex == 0时, 不跳过本次循环直接进入secondIndex的查找
            if (firstIndex > 0 && nums[firstIndex] == nums[firstIndex - 1])
                continue;
            
            // 当firstIndex位置的数据已经>0
            // 就说明 数组从此位置开始,  之后的所有数据都>0
            // 后面也就不存在 任意三个元素加为0的三元组
            // 所以直接跳出整个循环
            if (nums[firstIndex] > 0)
                break;
            
            // 走到这里, 就说明nums[firstIndex] 是整个数组的首元素 或 nums[firstIndex] != nums[firstIndex-1], 即nums[firstIndex]就是新相同元素序列的第一个元素
            // 就可以从firstIndex + 1位置, 开始尝试确认第二个元素
            int thirdIndex = numsSize - 1;
            int satTarget = -nums[firstIndex];
            for (int secondIndex = firstIndex + 1; secondIndex < numsSize - 1; secondIndex++) {
                // 相同的思路, 尝试确认第二个元素
                if (secondIndex > firstIndex + 1 && nums[secondIndex] == nums[secondIndex - 1])
                    continue;
                
                // 从数组尾, 遍历查找第三个元素
                while (secondIndex < thirdIndex && 
                       nums[secondIndex] + nums[thirdIndex] > satTarget)
                    thirdIndex--;
                
                if (secondIndex == thirdIndex)
                    break;
                    // 这意味着, nums[thirdIndex]最小时, 也没能找到目标 thirdIndex, 后续的遍历就不必了
             
                // 如果找到了, 就存储 记录
                if (nums[secondIndex] + nums[thirdIndex] == satTarget)
                    ret.push_back(vector<int>{nums[firstIndex], nums[secondIndex], nums[thirdIndex]});
            }
        }

        return ret;
    }
};