2-sum

  • 解法一: hash

从左往右扫描一遍，然后将数及对应坐标，存到map中。然后再扫描一遍即可，时间复杂度O(n)

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int,bool> mapping;
    for(int i = 0; i < nums.size(); ++i)
        mapping[nums[i]] = i;
    
    vector<int> results;
    for(int i = 0; i < nums.size(); i++){
        int gap = target - nums[i];
        if(mapping.find(gap) != mapping.end() && mapping[gap] > i){
            results.push_back(i);
            results.push_back(mapping[gap]);
            break;
        }
    }
    return results;
}

需要注意的是，对于含重复元素的序列，比如　numbers={ 2，2，5，6 }，target = 4 的情况，可能大家会想　mapping 里面的　< 2, 1 > 会将< 2, 0 > 覆盖掉，这样是不是就不行了？　其实覆盖也没有关系，后面扫描时用的是第一个２，hash 获得的元素位置是第二个 2。

  • 解法二：双指针扫描

将数组排序，然后双指针从前后往中间扫描，时间复杂度O(n*logn)

3-sum

解题思路：先排序，固定一个数，转化为　2-sum，利用双指针左右夹逼

//注意去重
vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> results;
    if(nums.size() < 3) return results;
    sort(nums.begin(),nums.end());
    const int target = 0;

    for(int i = 0; i < nums.size()-2; ++i){
        int j = i+1;
        if(i > 0 && nums[i] == nums[i-1]) continue;
        int k = nums.size() - 1;
        while(j < k){
            if(nums[i]+nums[j]+nums[k] < target){
                ++j;
                while(nums[j] == nums[j-1] && j < k) ++j; //去重
            }else if(nums[i]+nums[j]+nums[k] > target){
                --k;
                while(nums[k] == nums[k+1] && j < k) --k; //去重
            }else{
                results.push_back({nums[i],nums[j],nums[k]});
                ++j;
                --k;
                while(nums[j] == nums[j-1] && nums[k] == nums[k+1] && j < k) ++j; //去重
            }
        }
    }
    return results;
}

3-Sum Closest

与　3-Sum　解法类似，但不用考虑去重了。

int threeSumClosest(vector<int>& nums, int target) {
    int results = 0;
    sort(nums.begin(),nums.end());

    int min_gap = INT_MAX;
    for(auto a = nums.begin(); a!=prev(nums.end(),2); ++a){
        auto b = next(a);
        auto c = prev(nums.end(),1);
        while(b != c){
            int sum = *a + *b + *c;
            int gap = abs(sum - target);
            if(gap < min_gap){
                min_gap = gap;
                results = sum;
            }

            if(sum >target)
                --c;
            else
                ++b;
        }
    }
    return results;
}