資訊專欄INFORMATION COLUMN
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.
ExampleGiven 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]
Could you solve it in O(n2) runtime?
Solutionpublic 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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/69649.html
摘要：排序法復(fù)雜度時(shí)間空間思路解題思路和一樣，也是先對(duì)整個(gè)數(shù)組排序，然后一個(gè)外層循環(huán)確定第一個(gè)數(shù)，然后里面使用頭尾指針和進(jìn)行夾逼，得到三個(gè)數(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){ ...
摘要：題目鏈接，從小到大排序固定第一個(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(...
摘要：這個(gè)題和的做法基本一樣，只要在循環(huán)內(nèi)計(jì)算和最接近的和，并賦值更新返回值即可。 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...
摘要：雙指針?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ù)的位置，所以語(yǔ)句里面可以把和歸為同一個(gè)分支，因?yàn)榇嬖诎貜?fù)數(shù)的情況，所以要和一樣，指針前移替換。那么另一個(gè)分支，除了將后移，還要更新返回值。約束條件為的兩種寫法 Problem Give you an integer array (index from 0 to n-1, where n is the size of this array, va...
閱讀 1363·2021-11-16 11:44
閱讀 3838·2021-10-09 10:01
閱讀 1829·2021-09-24 10:31
閱讀 4056·2021-09-04 16:41
閱讀 2581·2021-08-09 13:45
閱讀 1300·2019-08-30 14:08
閱讀 1861·2019-08-29 18:32
閱讀 1699·2019-08-26 12:12
