两数之和 三数之和【基础算法精讲 01】

灵神算法基础算法精讲[01] : 

两数之和 三数之和【基础算法精讲 01】_哔哩哔哩_bilibili

167.两数之和 II - 输入有序数组

链接 : 

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路 : 

1. 采用双指针的思想，因为给出的数组是有序的，n  = len(numbers),定 l = 0,r = n-1;
2. 如果s = numbers[l] + numbers[r]  > target , 那么s要变小，则r--;
3. 如果s = numbers[l] + numbers[r]  < target , 那么s要变大，则l++;
4. 如果s = numbers[l] + numbers[r]  = target , 那么就得到结果了，则返回[l+1,r+1]即可;

代码(python):

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l = 0
        r = len(numbers)-1
        while True:
            s = numbers[l] + numbers[r]
            if s==target:
                break
            if s>target:
                r -= 1
            else :
                l += 1
        return [l+1,r+1]

代码(c++):

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l=0,r=numbers.size()-1;
        while(true){
            int s = numbers[l]+numbers[r];
            if(s==target) break;
            if(s>target) r--;
            else l++;
        }
        return {l+1,r+1};
    }
};

三数之和

链接 : 

三数之和

思路 ：

假设满足条件的三个数的下标分别为i , j, k，且默认i

先对数组进行排序，方便后面的操作

对i进行枚举，然后就是一个双指针的问题，令x=nums[i] , j=i+1 , k=n-1 ; 令 s = x + nums[j] + nums[k] , 剩下的就可以参考前一题中的思路：

1.如果s > 0  :  k--;

2.如果s<0  : j++

3.如果s=0 : 添加到结果中；

去重 ： 分别对i,j,k去重；

优化 : 如果相邻的三数之和>0，那么就可以直接break了，因为后面的只会加大

如果nums[i]+nums[n-1]+nums[n-2]<0,那么就continue,因为这是以i为起点的情况下s的最大值，如果小于0，那么直接continue,跳到下一个 i 上;

代码( python ):

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        # 排序
        # i
        ans = []
        n = len(nums)
        for i in range(n-2):
            x = nums[i]
            if i>0 and x==nums[i-1]:# 对x去重
                continue
            if x+nums[i+1]+nums[i+2]>0: # 优化
                break
            if x+nums[-2]+nums[-1]<0: # 优化
                continue
            j = i + 1
            k = n - 1
            while j < k:
                s = x + nums[j] + nums[k]
                if s>0:
                    k -= 1
                elif s < 0:
                    j += 1 
                else:
                    ans.append([x,nums[j],nums[k]])
                    j += 1
                    while jand nums[j]==nums[j-1]:# 对j去重
                        j+=1
                    k-=1
                    while jand nums[k]==nums[k+1]:# 对k去重
                        k-=1
        return ans

代码( c++ ) : 

class Solution {
public:
    vectorint>> threeSum(vector<int>& nums) {
    int n = nums.size();
    vectorint>> ans;
    sort(nums.begin(),nums.end());
    for(int i=0;i-2;i++)
    {
        int x = nums[i];
        if(x+nums[i+1]+nums[i+2] > 0) return ans;//如果三数和最小值大于0，那么直接返回
        if(x+nums[n-1]+nums[n-2]<0) continue;
        // 对a去重
        if(i>0 && nums[i] == nums[i-1]) continue;
        int left = i+1;
        int right = n-1;
        while(right>left)
        {
            int x = nums[i] + nums[left] + nums[right];
            if(x > 0) right--;
            else if(x < 0) left++;
            else 
            {
               ans.push_back(vector<int>{nums[i],nums[left],nums[right]});
               while(left-1]) right--;
               while(left < right && nums[left] == nums[left+1]) left ++; 
               left++;
               right--;
            }
        }
    }
    return ans;
    }
};

习题 : 

最接近的三数之和

链接:

 https://leetcode.cn/problems/3sum-closest/

思路 :  

与三数之和类似，详情请看代码 : 

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin() , nums.end());
        int n = nums.size(),mi = 1e5+7,ans = 0,s;
        for(int i=0;i-2;i++){
            int x = nums[i];
            if(i>0 && x==nums[i-1]) continue;// 优化一
            s = x + nums[i + 1] + nums[i + 2];
            if (s>target) { //优化二
                if (s-target
                break;
            }
            s = x + nums[n - 2] + nums[n - 1];
            if (s < target) { // 优化三
                if (target-s
                    mi = target-s;
                    ans = s;
                }
                continue;
            }
            int j=i+1,k=n-1;
            while(j
                int s = nums[j] + nums[k] + x;
                if(s==target) return s;
                else if(s>target){
                    if(s-target < mi){
                        mi = s-target;
                        ans = s;
                    }
                    k--;
                }
                else if(s
                    if(target-s < mi){
                        mi = target - s;
                        ans = s;
                    }
                    j++;
                }
            }
        }
        return ans;
    }
};

四数之和 : 

链接 : 

https://leetcode.cn/problems/4sum/description/

思路 : 和之前思路一样，双指针即可，加上去重和剪枝即可!!!

代码 : 

class Solution {
    public List> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List> ans = new ArrayList<>();
        int n = nums.length;
        for(int a=0;a3;a++){//枚举第一个数
            long x = nums[a];
            if(a>0 && x==nums[a-1]) continue;//优化一
            if(x+nums[a+1]+nums[a+2]+nums[a+3]>target) break;//优化二
            if(x+nums[n-3]+nums[n-2]+nums[n-1]continue; // 三
            for(int b=a+1;b2;b++){
                long y = nums[b];
                if(b>a+1 && y==nums[b-1]) continue;//四
                if(x+y+nums[b+1]+nums[b+2]>target) break;//五
                if(x+y+nums[n-2]+nums[n-1]continue;//六
                int c = b+1,d=n-1;
                while(c
                    long s = x+y+nums[c]+nums[d];
                    if(s>target) d--;
                    else if(s
                    else {
                        ans.add(List.of((int)x,(int)y,nums[c],nums[d]));
                        for(c++;c1];c++);
                        for(d--;d>c&&nums[d]==nums[d+1];d--);
                    }
                }
            } 
        }
        return ans;
        
    }
}

 统计和小于目标的下标对数目 : 

链接 : 
链接https://leetcode.cn/problems/count-pairs-whose-sum-is-less-than-target/

 思路 : 

双指针

代码 : 

class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        int ans = 0;
        int n = nums.size();
        sort(nums.begin(),nums.end());
        int i=0,j=n-1;
        while(i
            int s = nums[i]+nums[j];
            if(s
                ans += j-i;
                i++;
            }else {
                j--;
            }
        }
        return ans;
    }
};

有效三角形的个数 :

链接 : 

有效三角形的个数

思路 : 

双指针

代码 : 

class Solution {
public:
    int triangleNumber(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int k = 2; k < nums.size(); k++) {
            int c = nums[k];
            int i = 0; // a=nums[i]
            int j = k - 1; // b=nums[j]
            while (i < j) {
                if (nums[i] + nums[j] > c) {
                    // 由于 nums 已经从小到大排序
                    // nums[i]+nums[j] > c 同时意味着：
                    // nums[i+1]+nums[j] > c
                    // nums[i+2]+nums[j] > c
                    // ...
                    // nums[j-1]+nums[j] > c
                    // 从 i 到 j-1 一共 j-i 个
                    ans += j - i;
                    j--;
                } else {
                    // 由于 nums 已经从小到大排序
                    // nums[i]+nums[j] <= c 同时意味着
                    // nums[i]+nums[j-1] <= c
                    // ...
                    // nums[i]+nums[i+1] <= c
                    // 所以在后续的循环中，nums[i] 不可能作为三角形的边长，没有用了
                    i++;
                }
            }
        }
        return ans;
    }
};