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

資訊專欄INFORMATION COLUMN

[LintCode] 3Sum Smaller

AprilJ / 1009人閱讀

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;
    }
}

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

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/69649.html

相關(guān)文章

  • [Leetcode] 3Sum Smaller 三數(shù)較小和

    摘要：排序法復(fù)雜度時間空間思路解題思路和一樣，也是先對整個數(shù)組排序，然后一個外層循環(huán)確定第一個數(shù)，然后里面使用頭尾指針和進行夾逼，得到三個數(shù)的和。 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 評論0 收藏0

  • 3Sum Smaller

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

    Salamander 評論0 收藏0

  • [LintCode/LeetCode] 3Sum Closest

    摘要：這個題和的做法基本一樣，只要在循環(huán)內(nèi)計算和最接近的和，并賦值更新返回值即可。 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] 3Sum

    摘要：雙指針法的解法。然后用和夾逼找到使三數(shù)和為零的三數(shù)數(shù)列，放入結(jié)果數(shù)組。對于這三個數(shù)，如果循環(huán)的下一個數(shù)值和當(dāng)前數(shù)值相等，就跳過以避免中有相同的解。 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

  • [LintCode] Count of Smaller Number ［二分法的活用］

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

    2json 評論0 收藏0

發(fā)表評論

0條評論

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