国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

Yangyang / 542人閱讀

摘要:題目要求輸入一個整數數組,從中找到所有的三個整數組成一個數組,這三個整數的和為。要求不包括重復的結果思路一無這里使用了三個指針。先對數組進行排序。

題目要求
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]
]

輸入一個整數數組,從中找到所有的三個整數組成一個數組,這三個整數的和為0。要求不包括重復的結果

思路一:無hashset or hashmap

這里使用了三個指針。
先對數組進行排序。確定左側固定的指針,然后移動右側兩個直至找到三個值和為0.如果當前三個指針的值小于0,則將中間的指針右移至下一個不同的值,如果小于0,則將最右側指針左移至下一個不重復的值。一旦右側和中間的指針重合,移動左側指針至下一個不重復的值,并且初始化中間和右側的指針

    public List> threeSum2(int[] nums) {
           List> result = new ArrayList>();
        int length = nums.length;
        if(length<3){
            return result;
        }
        Arrays.sort(nums);

        int i = 0;
        while(i0) break;
            int j = i+1;
            int k = nums.length - 1;
            while(j=0){
                    //消去右側重復的數字
                    while(nums[k--] == nums[k] && j < k);
                }
                
                //消去和當前左指針相同的數字
                while(nums[i] == nums[++i] && i < nums.length - 2);
            }
            
        }
        return result;
    }
思路二:有hashmap/hashset

利用hashmap/hashset是為了避開重復的值,但是效率值明顯不如上一種方法高

public List> threeSum(int[] num) {
    Arrays.sort(num);
    List> list = new ArrayList>();
    HashSet> set = new HashSet>();
    for(int i=0;i l= new ArrayList();
                l.add(num[i]);
                l.add(num[j]);
                l.add(num[k]);
                if(set.add(l))
                list.add(l);
                j++;
                k--;
            }
            else if(num[i]+num[j]+num[k]<0)
            j++;
            else
            k--;
        }
    }
    return list;
}


想要了解更多開發技術,面試教程以及互聯網公司內推,歡迎關注我的微信公眾號!將會不定期的發放福利哦~

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

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

相關文章

  • 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 評論0 收藏0
  • leetcode 15 3Sum

    摘要:要求序列不重復。這個問題比較復雜的一點是,還要處理重復的數據。為了簡化我們的操作,我們先對數組進行預排序。排序之后,對于求兩個數和的問題,可以通過和兩個指針從兩邊查找,也簡化了操作時間。解法防止重復序列 題目詳情 Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0...

    FuisonDesign 評論0 收藏0
  • leetcode494. Target Sum

    摘要:為了尋找合適的正負號賦值,我們其實可以將數組分為兩個子集,其中一個子集中的數字都被賦予了正號,而另一個子集中的數字都被賦予了負號。如果二者的和不是一個偶數,就一定無法找到這樣的正負號集合使得其結果為。 題目要求 You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now yo...

    RobinTang 評論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 評論0 收藏0
  • [LintCode/LeetCode] 3Sum

    摘要:雙指針法的解法。然后用和夾逼找到使三數和為零的三數數列,放入結果數組。對于這三個數,如果循環的下一個數值和當前數值相等,就跳過以避免中有相同的解。 Problem Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplet...

    Sunxb 評論0 收藏0

發表評論

0條評論

Yangyang

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<