leetcode 18 4Sum

Vixb 发布于2019-08-16 11:03 / 611人阅读

摘要：题目详情输入一个长度为的整数数组和一个目标整数，我们需要找出是否存在个元素，使得的和等于。如果有，输出这样的非重复的元素序列。在求元素的时候可以通过左右指针减少查找时间。

题目详情

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.

输入一个长度为n的整数数组和一个目标整数target，我们需要找出是否存在4个元素a、b、c、d，使得abcd的和等于target。如果有，输出这样的非重复的元素序列。

For example, 输入数组S = [1, 0, -1, 0, -2, 2], 目标整数target = 0.
返回的结果集是：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

想法

本题的思路还是基于3Sum问题延伸出来的。

减治思想，如果通过遍历，每次锁定一个元素作为a元素，然后剩下的问题就变成了求三个数的和是否等于target，依次类推。

在求cd元素的时候可以通过左右指针减少查找时间。

解法

    public List> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List> res = new ArrayList>();
        int length = nums.length;
        if(length<4 || target > nums[length-1]*4 || target < nums[0]*4)return res;
        
        for(int i=0;i0 && nums[i] != nums[i-1])){
                for(int j=i+1;j tempTarget){
                                high--;
                            }else{
                                low++;
                            }
                        }
                    }
                }
                
            }
        }
        return res;
    }

云服务器 GPU云服务器 Leetcod LeetCode LeetCode_String leetcode_35_SearchIn

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

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

[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 2019-08-14 15:42 评论0 收藏0
[Leetcode] Two Sum, 3Sum,4Sum,4SumII,3Sum Closet

摘要：解题思路题目要求两个数和等于，返回其题目说明不会有重复情况，所以我们一旦发现符合情况的，就可以直接结束循环并返回。特殊情况就是正好等于，那肯定是最接近的情况，直接返回即可。 Two SumGiven an array of integers, return indices of the two numbers such that they add up to a specific ta...

EddieChan 2019-08-19 10:45 评论0 收藏0
leetcode14 4sum

摘要：这里需要注意及时处理掉重复的情况。那么就需要尽可能排除不可能的情况来提高计算效率。因为数组已经被排序，所以可以根据数组中元素的位置判断接下来的情况是否有可能合成目标值。题目要求此处为原题地址 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d =...

MoAir 2019-08-16 10:31 评论0 收藏0
[Leetcode] 3Sum 4Sum 3Sum Closet 多数和

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

trigkit4 2019-08-14 12:29 评论0 收藏0
leetcode 部分解答索引（持续更新～）

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

leo108 2019-08-15 14:26 评论0 收藏0