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

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] 3Sum

Sunxb / 1520人閱讀

摘要:雙指針法的解法。然后用和夾逼找到使三數和為零的三數數列,放入結果數組。對于這三個數,如果循環的下一個數值和當前數值相等,就跳過以避免中有相同的解。

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 triplets in the array which gives the sum of zero.

Notice

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

The solution set must not contain duplicate triplets.

Example

For example, given array S = {-1 0 1 2 -1 -4}, A solution set is:

(-1, 0, 1)
(-1, -1, 2)
Note

雙指針法:O(n^2)的解法。
遍歷第一個到倒數第三個數nums[i],作為三數數列的隊首;
nums[i]后面的一個數作為三數數列中的第二個數nums[left]
數組中最后一個數nums[nums.length-1]作為三數數列中的第三個數nums[right]
然后用leftright夾逼找到使三數和為零的三數數列,放入結果數組res
對于這三個數,如果循環的下一個數值和當前數值相等,就跳過以避免res中有相同的解。

Solution
public class Solution {
    public ArrayList> threeSum(int[] A) {
        ArrayList> res = new ArrayList();
        if (A.length < 3) return null;
        Arrays.sort(A);
        for (int i = 0; i <= A.length-3; i++) {
            int left = i+1, right = A.length-1;
            if (i != 0 && A[i] == A[i-1]) continue;
            while (left < right) {
                int sum = A[i]+A[left]+A[right];
                if (sum == 0) {
                    ArrayList temp = new ArrayList();
                    temp.add(A[i]);
                    temp.add(A[left]);
                    temp.add(A[right]);
                    res.add(temp);
                    left++;
                    right--;
                    while (left < right && A[left] == A[left-1]) left++;
                    while (left < right && A[right] == A[right+1]) right--;
                }
                else if (sum < 0) left++;
                else right--;
            }
        }
        return res;
    }
}
update 2018-9
class Solution {
    public List> threeSum(int[] nums) {
        List> res = new ArrayList<>();
        if (nums == null || nums.length < 3) return res;
        
        Arrays.sort(nums);

        for (int i = 0; i < nums.length-2; i++) {
            if (i == 0 || (i > 0 && nums[i] != nums[i-1])) {
                int sum = 0-nums[i];
                int l = i+1, r = nums.length-1;
                
                while (l < r) {
                    int curSum = nums[l]+nums[r];
                    if (curSum == sum) {
                        res.add(Arrays.asList(nums[i], nums[l++], nums[r--]));
                        while (l < r && nums[l] == nums[l-1]) l++;
                        while (l < r && nums[r] == nums[r+1]) r--;
                    } else if (curSum < sum) {
                        l++;
                    } else {
                        r--;
                    }
                }
                
            }
        }
        return res;
    }
}

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

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

相關文章

  • [LintCode/LeetCode] 3Sum Closest

    摘要:這個題和的做法基本一樣,只要在循環內計算和最接近的和,并賦值更新返回值即可。 Problem 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 intege...

    ShevaKuilin 評論0 收藏0
  • [LintCode/LeetCode] Word Break

    Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...

    dunizb 評論0 收藏0
  • [LintCode/LeetCode] First Unique Character in a S

    Problem Given a string, find the first non-repeating character in it and return its index. If it doesnt exist, return -1. Example Given s = lintcode, return 0. Given s = lovelintcode, return 2. Tags A...

    Xufc 評論0 收藏0
  • [LintCode/LeetCode] Find Median From / Data Stream

    摘要:建立兩個堆,一個堆就是本身,也就是一個最小堆另一個要寫一個,使之成為一個最大堆。我們把遍歷過的數組元素對半分到兩個堆里,更大的數放在最小堆,較小的數放在最大堆。同時,確保最大堆的比最小堆大,才能從最大堆的頂端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...

    zxhaaa 評論0 收藏0
  • [LintCode/LeetCode] Implement Trie

    摘要:首先,我們應該了解字典樹的性質和結構,就會很容易實現要求的三個相似的功能插入,查找,前綴查找。既然叫做字典樹,它一定具有順序存放個字母的性質。所以,在字典樹的里面,添加,和三個參數。 Problem Implement a trie with insert, search, and startsWith methods. Notice You may assume that all i...

    付永剛 評論0 收藏0

發表評論

0條評論

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