[Leetcode] 3Sum Smaller 三數較小和

tomato 發布于2019-08-14 12:35 / 418人閱讀

摘要：排序法復雜度時間空間思路解題思路和一樣，也是先對整個數組排序，然后一個外層循環確定第一個數，然后里面使用頭尾指針和進行夾逼，得到三個數的和。

3Sum Smaller

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
For example, given nums = [-2, 0, 1, 3], and target = 2.
Return 2. Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]

Follow up: Could you solve it in O(n2) runtime?

排序法 復雜度

時間 O(N^2) 空間 O(1)

思路

解題思路和3SUM一樣，也是先對整個數組排序，然后一個外層循環確定第一個數，然后里面使用頭尾指針left和right進行夾逼，得到三個數的和。如果這個和大于或者等于目標數，說明我們選的三個數有點大了，就把尾指針right向前一位（因為是排序的數組，所以向前肯定會變小）。如果這個和小于目標數，那就有right - left個有效的結果。為什么呢？因為假設我們此時固定好外層的那個數，還有頭指針left指向的數不變，那把尾指針向左移0位一直到左移到left之前一位，這些組合都是小于目標數的。

代碼

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        // 先將數組排序 
        Arrays.sort(nums);
        int cnt = 0;
        for(int i = 0; i < nums.length - 2; i++){
            int left = i + 1, right = nums.length - 1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                // 如果三個數的和大于等于目標數，那將尾指針向左移
                if(sum >= target){
                    right--;
                // 如果三個數的和小于目標數，那將頭指針向右移
                } else {
                    // right - left個組合都是小于目標數的
                    cnt += right - left;
                    left++;
                }
            }
        }
        return cnt;
    }
}

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

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

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

LeetCode 之 JavaScript 解答第十五題 —— 三數之和（3Sum）

摘要：如果三個數據相加等于了，就存儲該三個值且更新和指針。邊界條件判斷數組內元素是否都為整數或負數，直接返回。判斷和指針的大小關系。在原來數組上進行排序，不生成副本。 Time：2019/4/3Title:3SumDifficulty: mediumAuthor:小鹿題目三：ADD Two Numbers Given an array?nums?of?n?integers, are the...

Wildcard 2019-08-23 16:45 評論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 2019-08-14 15:42 評論0 收藏0
3Sum Smaller

摘要：題目鏈接，從小到大排序固定第一個數字，從后面的數字里選第二個第三個后兩個數字，用來找，從開始因為所有之間的數和組合都 3Sum Smaller 題目鏈接：https://leetcode.com/problems... sort，從小到大排序固定第一個數字index = i，從后面的數字里選第二個第三個后兩個數字，用2 points來找，從j = i + 1, k = len(...

Salamander 2019-08-14 17:19 評論0 收藏0
思維導圖整理大廠面試高頻數組補充1: 最接近的三數之和和三數之和的兩個不同之處, 力扣16

摘要：此專欄文章是對力扣上算法題目各種方法的總結和歸納整理出最重要的思路和知識重點并以思維導圖形式呈現當然也會加上我對導圖的詳解目的是為了更方便快捷的記憶和回憶算法重點不用每次都重復看題解畢竟算法不是做了一遍就能完全記住的所 ...

longmon 2021-11-12 10:36 評論0 收藏0
[LintCode] 3Sum Smaller

Problem Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 = target) return 0; int count = 0; for (int i = 0; i < nums.length-2; i++) { ...

AprilJ 2019-08-15 18:09 評論0 收藏0