资讯专栏INFORMATION COLUMN

[Leetcode] Two Sum, 3Sum,4Sum,4SumII,3Sum Closet

EddieChan / 3248人阅读

摘要:解题思路题目要求两个数和等于,返回其题目说明不会有重复情况,所以我们一旦发现符合情况的,就可以直接结束循环并返回。特殊情况就是正好等于,那肯定是最接近的情况,直接返回即可。

Two Sum
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.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

1.解题思路

题目要求两个数和等于target,返回其index.题目说明不会有重复情况,所以我们一旦发现符合情况的,就可以直接结束循环并返回。
利用HashMap,边遍历存储,边寻找。当给定一个数n,只要看target-n是否在map中即可,如果存在,则取出其value - 即该数的下标。

2.代码

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res=new int[2];
        if(nums.length==0) return res;
        HashMap hm=new HashMap();
        for(int i=0;i

3Sum
Given an array S of n integers, are there elements a, b, c in S 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.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

1.解题思路

本题要求三个数的和为0,其实就是固定一个数n之后,找两个数和为0-n,所以就转化为求两个数的和,那我们很容易想到使用二分法。
注意点:本题需要排除重复值,
1)固定的数下标为i,则要从i+1开始寻找后两个数;
2)如果数组中包含重复的数,则为了保证结果不出现重复,我们每次遇到重复的数需要跳过。

2.代码

public class Solution {
    List> res =new ArrayList>();
    public List> threeSum(int[] nums) {
      
       Arrays.sort(nums);
      
       for(int i=0;i0&&nums[i]==nums[i-1]) continue; //避免重复
           twoSum(0-nums[i],nums,i+1,nums.length-1);
       }
       return res;
    }
    private void twoSum(int target,int[] nums, int start,int end){
        
        int i=start,j=end;
        while(i subres=new ArrayList();
            int sum=nums[i]+nums[j];
            if(sum==target){
                subres.add(0-target);
                subres.add(nums[i]);
                subres.add(nums[j]);
                res.add(subres);
                
               do {
                    i++;
                }while(i < end && nums[i] == nums[i-1]);
                do {
                    j--;
                } while(j >= 0 && nums[j] == nums[j+1]);
            }
            else if(sum

4Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

1.解题思路

4Sum,就是在3Sum基础上再嵌套一层,注意点也是要避免重复。

2.代码

public class Solution {
    ArrayList> res = new ArrayList>();
    public List> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        for(int i=0;i0&&nums[i]==nums[i-1]) continue;
              res.addAll(threesum(target-nums[i],nums,i+1));
        }
        return res;
    }
    private List> threesum(int target,int[] nums,int start){
        ArrayList> res = new ArrayList>();
        int first=start-1;
        for(int i=start;istart&&nums[i]==nums[i-1]) continue;
            res.addAll(twosum(target-nums[i],nums,i+1,first));
        }
        return res;
    }
    private List> twosum(int target,int[] nums,int start,int first){
        List> res =new ArrayList>();
        int second=start-1;
        int i=start;
        int j=nums.length-1;
        while(i subres =new ArrayList();
            int sum=nums[i]+nums[j];
            if(sum==target){
                subres.add(nums[first]);
                subres.add(nums[second]);
                subres.add(nums[i]);
                subres.add(nums[j]);
                res.add(subres);
                i++;
                while(i=0&&nums[j]==nums[j+1]){
                    j--;
                }
            }
            else if(sum>target) j--;
            else i++;
            
        }
        return res;
    }
}

3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

1.解题思路

与3Sum相似,只不过本次是要寻找最接近target的3个数之和,我们需要维护minDiff和closetSum两个变量。
但是本题题目说明不许考虑重复。 特殊情况就是sum正好等于target,那肯定是最接近的情况,直接返回即可。

2.代码

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if(nums.length==0) return 0;
        int minDiff=Integer.MAX_VALUE;
        int closet=0;
        Arrays.sort(nums);
        for(int i=0;itarget){
                    right--;
                }
                else return sum;
            }
        }
        return closet;
    }
}

4Sum II

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

1.解题思路

本题从1个数组扩展到了4个数组,求的是有多少组4数之和等于target的,我们把问题分为两个数一组,假设当前两个数A[i]+B[j],那我们其实就是要在C和D中求是否存在和为0-A[i]-B[j],如果存在则返回存在的个数。想到用HashMap,存储.

2.代码

public class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        if(A.length==0||B.length==0||C.length==0||D.length==0) return 0;
        Map map=new HashMap();
        int count=0;
        for(int i=0;i           
               
                                           
                       
                 

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/76392.html

相关文章

  • [Leetcode] 3Sum 4Sum 3Sum Closet 多数和

    摘要:为了避免得到重复结果,我们不仅要跳过重复元素,而且要保证找的范围要是在我们最先选定的那个数之后的。而计算则同样是先选一个数,然后再剩下的数中计算。 2Sum 在分析多数和之前,请先看Two Sum的详解 3Sum 请参阅:https://yanjia.me/zh/2019/01/... 双指针法 复杂度 时间 O(N^2) 空间 O(1) 思路 3Sum其实可以转化成一个2Sum的题,...

    trigkit4 评论0 收藏0
  • 【LC总结】K Sum (Two Sum I II/3Sum/4Sum/3Sum Closest)

    摘要:找符合条件的总数。双指针区间考虑边界,长度,为空,等。之后的范围用双指针和表示。若三个指针的数字之和为,加入结果数组。不要求,所以不用判断了。同理,头部两个指针向后推移,后面建立左右指针夹逼,找到四指针和为目标值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...

    awesome23 评论0 收藏0
  • leetcode 部分解答索引(持续更新~)

    摘要:前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写~现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。 顺序整理 1~50 1...

    leo108 评论0 收藏0
  • [LeetCode] 4Sum & 4Sum II

    摘要:和方法一样,多一个数,故多一层循环。完全一致,不再赘述, 4Sum Problem Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which ...

    sydMobile 评论0 收藏0
  • leetcode 18 4Sum

    摘要:题目详情输入一个长度为的整数数组和一个目标整数,我们需要找出是否存在个元素,使得的和等于。如果有,输出这样的非重复的元素序列。在求元素的时候可以通过左右指针减少查找时间。 题目详情 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target...

    Vixb 评论0 收藏0

发表评论

0条评论

EddieChan

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<