[LintCode] 3Sum Smaller

AprilJ 發(fā)布于2019-08-15 18:09 / 1019人閱讀

Problem

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.

Example

Given nums = [-2,0,1,3], target = 2, return 2.

Explanation:

Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]

Challenge

Could you solve it in O(n2) runtime?

Solution

public class Solution {
    /**
     * @param nums:  an array of n integers
     * @param target: a target
     * @return: the number of index triplets satisfy the condition nums[i] + nums[j] + nums[k] < target
     */
    public int threeSumSmaller(int[] nums, int target) {
        // Write your code here
        if (nums.length < 3) return 0;
        Arrays.sort(nums);
        if (nums[0] >= target) return 0;
        int count = 0;
        for (int i = 0; i < nums.length-2; i++) {
            int start = i+1, end = nums.length-1;
            int sum = target - nums[i];
            while (start < end) {
                if (nums[start] + nums[end] < sum) {
                    count += end-start;
                    start++;
                } else {
                    end--;
                }
            }
        }
        return count;
    }
}

GPU云服務器云服務器 Smaller LintCode LintCode134_LRU

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

轉載請注明本文地址：http://systransis.cn/yun/69649.html

[Leetcode] 3Sum Smaller 三數較小和

摘要：排序法復雜度時間空間思路解題思路和一樣，也是先對整個數組排序，然后一個外層循環(huán)確定第一個數，然后里面使用頭尾指針和進行夾逼，得到三個數的和。 3Sum Smaller Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 = target){ ...

tomato 2019-08-14 12:35 評論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
[LintCode/LeetCode] 3Sum Closest

摘要：這個題和的做法基本一樣，只要在循環(huán)內計算和最接近的和，并賦值更新返回值即可。 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 2019-08-14 15:42 評論0 收藏0
[LintCode/LeetCode] 3Sum

摘要：雙指針法的解法。然后用和夾逼找到使三數和為零的三數數列，放入結果數組。對于這三個數，如果循環(huán)的下一個數值和當前數值相等，就跳過以避免中有相同的解。 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
[LintCode] Count of Smaller Number ［二分法的活用］

摘要：由于這道題目不是查找而是選擇第一個的數的位置，所以語句里面可以把和歸為同一個分支，因為存在包含重復數的情況，所以要和一樣，指針前移替換。那么另一個分支，除了將后移，還要更新返回值。約束條件為的兩種寫法 Problem Give you an integer array (index from 0 to n-1, where n is the size of this array, va...

2json 2019-08-14 15:16 評論0 收藏0