[leetcode] 1/15/16/18 2sum/3Sum

两数之和

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].

这题给定一个数组， 返回 满足 a + b = target 规则的 a,b 下标。

1. 暴力的话 的时间内check 这个规则就ok了。
2. 如果这个数组是个排序数组， 那么可以使用双指针 左右夹逼，因为数组有序， a+b 在 [a:b]区间内 ， a往右会导致 结果变大， b往左，会导致结果变小。这样的时间内就可以找到 a+b = target 的情况。算上排序的时间复杂度，假设是快排 最终时间复杂度为 ，空间复杂度为
3. 我们借助哈希表 是否可以牺牲一点空间来获得的速度。
   当我们访问a 点时， 我们把 target- a 也就是 b 点的值 存储在哈希表中当作key, a点的下标当作value。那么如果b 点真的存在， 那么遍历到b 点时，自然可以在哈希表中找到 之前存储的a点下标。

#include <unordered_map>
using namespace std;

class Solution {
public:
    // a+b = target --> b = target -a 
    //  b : index(a)
    
    vector<int> twoSum(vector<int>& nums, int target) {
        
        unordered_map<int,int> up;
        vector<int> ans;
        for(int a = 0; a< nums.size();a++){
            if (up.find(nums[a]) != up.end()){
                ans.push_back(up[nums[a]]);
                ans.push_back(a);
                return ans;
            } 
            up[target-nums[a]] = a;
        }

    }
};

image.png

三数之和

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.

Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[ [-1, 0, 1],
[-1, -1, 2]]

这题的规则变成 a+b+c =target

1. 暴力检查这个规则 -->
2. 如果我们固定住 c和 target ， 这题就可以转化为 n 个 2sum 的问题，由上题我们知道 2sum 可以在 O(n) 的时间内用哈希表解决， 那么最终就是 的时间，但是要花费的空间， 如果2sum 使用双指针 两边夹逼 最终是 =的时间复杂度，但是不需要额外开辟空间。

所以 我们这里固定住 C后 ，对a+b 使用双指针 两边夹的办法。
排序后， 我们很容易找到 a,b,c在排序数组上的关系, 如下图

image.png

这题要考虑一个去重的问题，我这里处理的比较简单。

if not ans or (ans and ans[-1] != temp):
      ans.append(temp)

完整代码

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        nums = sorted(nums)
        cur = 0
        while cur < len(nums)-2:
            if cur>0 and nums[cur] == nums[cur-1]:
                cur+=1
                continue      
            i = cur+1
            j = len(nums) - 1
            while i < j: 
                if nums[i]+ nums[j] == -nums[cur]:
                    temp = [nums[cur],nums[i],nums[j]]
                    if not ans or (ans and ans[-1] != temp):
                        ans.append(temp)
                    i+=1
                    j-=1
                elif nums[i]+ nums[j] > -nums[cur]:
                    j-=1
                else:
                    i+=1    
            cur+=1
        return ans

image.png

3 sum closest

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

现在 规则变成了 a+b+c+ gap = target ,输出当gap 最小的时候，a,b,c的和。
实际上 这题和上一题并没有什么区别， 仍然是 一样的判断条件，只是每次根据gap = target -a- b- c 更新最小的结果就ok了。
代码如下：

class Solution:
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        
        nums= sorted(nums)
        _min = float("inf")
        _distance = float("inf")
        cur = 0
        
        while cur < len(nums)-2:
            i = cur+1
            j = len(nums)-1
            while i < j:
                distance = abs(target - (nums[i] +nums[j] +nums[cur]))
                if _distance > distance:
                    _distance = distance
                    _min =   nums[i] +nums[j] +nums[cur]
                    
                if target > nums[i] +nums[j] + nums[cur]:
                    i+=1
                elif target < nums[i] + nums[j] + nums[cur]:
                    j-=1
                else:
                    return nums[i] + nums[j] + nums[cur]
                

            cur+=1
        return _min
            
    

image.png

四数之和

将 4 sum 转化为 3 sum 在转化为 2 sum
要注意 去重的问题。

#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        // res 
        vector<vector<int>> res;        
        if(nums.size() < 4){
            return res;
        }
        // sort
        sort(nums.begin(),nums.end());
        
        int c= 0, d=0;
        
        for(int a = 0; a < nums.size()-3; a++){
            // 3 sum 
            if(a==0 || (a > 0 && nums[a] != nums[a-1]) ){
                for(int b = a+1; b < nums.size()-2; b++){
                    //2 sum 
                    if(b == a+1 || (b > a+1 && nums[b] != nums[b-1]) ){
                        c = b+1;
                        d = nums.size()-1;
                        while(c < d){
                            
                            if (c> b+1 && nums[c] ==nums[c-1]){
                                c++;
                                continue;
                            }
                            if(d < nums.size()-1 && nums[d] == nums[d+1]){
                                d--;
                                continue;
                            }
                            
                            if(nums[a] + nums[b] + nums[c]+ nums[d] > target){d--;}
                            else if(nums[a] + nums[b] + nums[c] + nums[d] < target){c++;}
                            else{
                                res.push_back(vector<int>{nums[a],nums[b],nums[c],nums[d]});
                                c++;d--;
                            }  
                        }

                        
                    }
                }
            }
        } 
       
        
        return res;
        
    }
};

image.png