leetcode 15 3Sum

FuisonDesign 發布于2019-08-16 11:03 / 776人閱讀

摘要：要求序列不重復。這個問題比較復雜的一點是，還要處理重復的數據。為了簡化我們的操作，我們先對數組進行預排序。排序之后，對于求兩個數和的問題，可以通過和兩個指針從兩邊查找，也簡化了操作時間。解法防止重復序列

題目詳情

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.

給定一個整數數組s，我們要找出s中是否有三個不同元素的加和等于0，如果有，輸出所有滿足條件的序列。要求序列不重復。

For example, 輸入數組S = [-1, 0, 1, 2, -1, -4],
返回的結果集應該是：
[
[-1, 0, 1],
[-1, -1, 2]
]

想法

通過減治的思想，我們可把三個數求和的問題，減治為對于數組中不重復的元素nums[i],求兩個數的和等于-nums[i]的過程。

這個問題比較復雜的一點是，還要處理重復的數據。為了簡化我們的操作，我們先對數組進行預排序。

經歷了預排序，我們判斷一個元素是否重復，只需要比較它和之前位置的元素是否相等就可以了。

排序之后，對于求兩個數和的問題，可以通過low和high兩個指針從兩邊查找，也簡化了操作時間。

解法

    public List> threeSum(int[] nums) {
        int length = nums.length;
         List> res = new  ArrayList>();
         Arrays.sort(nums);
        
         for(int i=0;i0 && nums[i] != nums[i-1])){
                 int low = i+1;
                 int high = length-1;
                 int target = -nums[i];
                 
                 while(low < high){
                     if(nums[low]+nums[high] == target){
                         res.add(Arrays.asList(nums[i], nums[low], nums[high]));
                         while(low < high && nums[low] == nums[low+1])low++;
                         while(low < high && nums[high] == nums[high-1])high--;
                         low++;
                         high--;
                     }else if(nums[low]+nums[high] < target){
                         low++;
                     }else{
                         high--;
                     }
                 }
             }
         }
        
        
        return res;
    }

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/70984.html

leetcode15 3Sum 從數組中找到三個整數，它們的和為0

摘要：題目要求輸入一個整數數組，從中找到所有的三個整數組成一個數組，這三個整數的和為。要求不包括重復的結果思路一無這里使用了三個指針。先對數組進行排序。題目要求 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 i...

Yangyang 2019-08-14 18:03 評論0 收藏0
leetcode16 3Sum Closest

摘要：返回這三個值的和。思路一三指針這里的思路和是一樣的，就是用三個指針獲得三個值并計算他們的和。題外話鑒于這一題的核心思路和leetcode15的思路相同，可以先寫一下15題并參考一下我之前的一篇博客題目要求 Given an array S of n integers, find three integers in S such that the sum is closest to...

Blackjun 2019-08-14 18:07 評論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
leetcode 16 3Sum Closest

摘要：題目詳情給定一個整數數組，我們需要找出數組中三個元素的加和，使這個加和最接近于輸入的數值。返回這個最接近的加和。找后兩個元素的時候，使用左右指針從兩端查找。題目詳情 Given an array S of n integers, find three integers in S such that the sum is closest to a given number, targe...

atinosun 2019-08-16 11:03 評論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