資訊專欄INFORMATION COLUMN
摘要：排序法復(fù)雜度時(shí)間空間思路解題思路和一樣，也是先對(duì)整個(gè)數(shù)組排序，然后一個(gè)外層循環(huán)確定第一個(gè)數(shù)，然后里面使用頭尾指針和進(jìn)行夾逼，得到三個(gè)數(shù)的和。
3Sum Smaller
排序法 復(fù)雜度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?
時(shí)間 O(N^2) 空間 O(1)
思路解題思路和3SUM一樣，也是先對(duì)整個(gè)數(shù)組排序，然后一個(gè)外層循環(huán)確定第一個(gè)數(shù)，然后里面使用頭尾指針left和right進(jìn)行夾逼，得到三個(gè)數(shù)的和。如果這個(gè)和大于或者等于目標(biāo)數(shù)，說(shuō)明我們選的三個(gè)數(shù)有點(diǎn)大了，就把尾指針right向前一位（因?yàn)槭桥判虻臄?shù)組，所以向前肯定會(huì)變?。Ｈ绻@個(gè)和小于目標(biāo)數(shù)，那就有right - left個(gè)有效的結(jié)果。為什么呢？因?yàn)榧僭O(shè)我們此時(shí)固定好外層的那個(gè)數(shù)，還有頭指針left指向的數(shù)不變，那把尾指針向左移0位一直到左移到left之前一位，這些組合都是小于目標(biāo)數(shù)的。
代碼public class Solution {
public int threeSumSmaller(int[] nums, int target) {
// 先將數(shù)組排序
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];
// 如果三個(gè)數(shù)的和大于等于目標(biāo)數(shù)，那將尾指針向左移
if(sum >= target){
right--;
// 如果三個(gè)數(shù)的和小于目標(biāo)數(shù)，那將頭指針向右移
} else {
// right - left個(gè)組合都是小于目標(biāo)數(shù)的
cnt += right - left;
left++;
}
}
}
return cnt;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64579.html
摘要：如果三個(gè)數(shù)據(jù)相加等于了，就存儲(chǔ)該三個(gè)值且更新和指針。邊界條件判斷數(shù)組內(nèi)元素是否都為整數(shù)或負(fù)數(shù)，直接返回。判斷和指針的大小關(guān)系。在原來(lái)數(shù)組上進(jìn)行排序，不生成副本。 Time：2019/4/3Title:3SumDifficulty: mediumAuthor:小鹿 題目三：ADD Two Numbers Given an array?nums?of?n?integers, are the...
摘要：雙指針?lè)ǖ慕夥?。然后用和夾逼找到使三數(shù)和為零的三數(shù)數(shù)列，放入結(jié)果數(shù)組。對(duì)于這三個(gè)數(shù)，如果循環(huán)的下一個(gè)數(shù)值和當(dāng)前數(shù)值相等，就跳過(guò)以避免中有相同的解。 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...
摘要：題目鏈接，從小到大排序固定第一個(gè)數(shù)字，從后面的數(shù)字里選第二個(gè)第三個(gè)后兩個(gè)數(shù)字，用來(lái)找，從開始因?yàn)樗兄g的數(shù)和組合都 3Sum Smaller 題目鏈接：https://leetcode.com/problems... sort，從小到大排序 固定第一個(gè)數(shù)字index = i，從后面的數(shù)字里選第二個(gè)第三個(gè) 后兩個(gè)數(shù)字，用2 points來(lái)找，從j = i + 1, k = len(...
摘要：此專欄文章是對(duì)力扣上算法題目各種方法的總結(jié)和歸納整理出最重要的思路和知識(shí)重點(diǎn)并以思維導(dǎo)圖形式呈現(xiàn)當(dāng)然也會(huì)加上我對(duì)導(dǎo)圖的詳解目的是為了更方便快捷的記憶和回憶算法重點(diǎn)不用每次都重復(fù)看題解畢竟算法不是做了一遍就能完全記住的所 ...
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++) { ...
閱讀 1710·2021-11-12 10:36
閱讀 1628·2021-11-12 10:36
閱讀 3452·2021-11-02 14:46
閱讀 3822·2019-08-30 15:56
閱讀 3576·2019-08-30 15:55
閱讀 1469·2019-08-30 15:44
閱讀 1056·2019-08-30 14:00
閱讀 2744·2019-08-29 18:41
