3Sum Smaller

Salamander 發(fā)布于2019-08-14 17:19 / 3403人閱讀

摘要：題目鏈接，從小到大排序固定第一個數(shù)字，從后面的數(shù)字里選第二個第三個后兩個數(shù)字，用來找，從開始因為所有之間的數(shù)和組合都

3Sum Smaller

題目鏈接：https://leetcode.com/problems...

sort，從小到大排序

固定第一個數(shù)字index = i，從后面的數(shù)字里選第二個第三個

后兩個數(shù)字，用2 points來找，從j = i + 1, k = len() - 1開始：

if n[j] + n[k] < target - n[i]: count += (k-i), j++
因為所有(j+1, k)之間的數(shù)和n[j]組合都< target - n[i]

if n[j] + n[k] >= target - n[i]: k--

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if(nums == null || nums.length < 3) return 0;
        // sort first
        Arrays.sort(nums);
        /* enumerate 1st num: k
         * 2 points find 2nd, 3rd
         * initial: i = k + 1, j = len(nums) - 1
         * case 1: n[i] + n[j] < target - n[k]: count += j - i, i++
         * case 2: > : j--
         */
        int count = 0;
        for(int k = 0; k < nums.length - 2; k++) {
            int i = k + 1, j = nums.length - 1;
            while(i < j) {
                if(nums[i] + nums[j] >= target - nums[k]) j--;
                else {
                    count += j - i;  i++;
                }
            }
        }
        return count;
    }
}

云服務器 GPU云服務器 Smaller

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

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

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

摘要：排序法復雜度時間空間思路解題思路和一樣，也是先對整個數(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 2019-08-14 12:35 評論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
[Leetcode] 3Sum 4Sum 3Sum Closet 多數(shù)和

摘要：為了避免得到重復結果，我們不僅要跳過重復元素，而且要保證找的范圍要是在我們最先選定的那個數(shù)之后的。而計算則同樣是先選一個數(shù)，然后再剩下的數(shù)中計算。 2Sum 在分析多數(shù)和之前，請先看Two Sum的詳解 3Sum 請參閱：https://yanjia.me/zh/2019/01/... 雙指針法復雜度時間 O(N^2) 空間 O(1) 思路 3Sum其實可以轉(zhuǎn)化成一個2Sum的題，...

trigkit4 2019-08-14 12:29 評論0 收藏0
[Leetcode] Two Sum, 3Sum,4Sum,4SumII,3Sum Closet

摘要：解題思路題目要求兩個數(shù)和等于，返回其題目說明不會有重復情況，所以我們一旦發(fā)現(xiàn)符合情況的，就可以直接結束循環(huán)并返回。特殊情況就是正好等于，那肯定是最接近的情況，直接返回即可。 Two SumGiven an array of integers, return indices of the two numbers such that they add up to a specific ta...

EddieChan 2019-08-19 10:45 評論0 收藏0
【LC總結】K Sum (Two Sum I II/3Sum/4Sum/3Sum Closest)

摘要：找符合條件的總數(shù)。雙指針區(qū)間考慮邊界，長度，為空，等。之后的范圍用雙指針和表示。若三個指針的數(shù)字之和為，加入結果數(shù)組。不要求，所以不用判斷了。同理，頭部兩個指針向后推移，后面建立左右指針夾逼，找到四指針和為目標值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...

awesome23 2019-08-14 15:50 評論0 收藏0