大家好,我是熊哥。
今天给大家带来一道与数组相关的高频面试题,这道题被IBM、谷歌和高盛等互联网大厂作为面试题考过,即力扣上的第 259 题-较小的三数之和和领扣上的第 918 题-三数之和小于。
本文主要介绍排序 + 二分查找和排序 + 对撞指针等三种方法来解答此题,供大家参考,希望对大家有所帮助。
给定一个长度为 n 的整数数组和一个目标值 target,寻找能够使条件
nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k
个数(0 <= i < j < k < n)。
示例及进阶
本题很容易想到通过暴力枚举去做。
按照题目的意思,遍历(三次)整个数组,找出满足条件的解即可。
C
int threeSumSmaller(int* nums, int numsSize, int target){
int cnt = 0;
for (int i = 0; i < numsSize - 2; ++i) {
for (int j = i + 1; j < numsSize - 1; ++j) {
for (int k = j + 1; k < numsSize; ++k) {
if (nums[i] + nums[j] + nums[k] < target) {
cnt++;
}
}
}
}
return cnt;
}
时间复杂度:O(n^3),其中 n 是数组的长度。
空间复杂度:O(1),未开辟额外存储空间。
力扣上运行结果
由于采用暴力法,时间复杂度为 O(n^3),时间复杂度太高,导致在力扣上运行超时(领扣上不会)。
遇到查找相关的题目,很容易想到二分查找法去求解,由于本题没有说明数组是有序的,因此首先需要对数组进行排序,再用二分查找。
以 nums = [-2,0,1,3], target = 2 为例,如下图示。
例子
由于 nums 本身就是有序的,所以不需要在排序了。
首先固定 i 和 j,然后再在(j, numsSize - 1]中查找满足条件的 k;
确定查找区间
根据 nums[mid]与 target - nums[i] - nums[j]的大小关系,缩短查找区间;
缩小查找范围
然后再确定满足条件的三元组的对数。
确定合适的三元组的对数
采用排序 + 二分查找法,完整查找过程,如下动图示:
查找过程(排序 + 二分法)
C
int comp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int threeSumSmaller(int* nums, int numsSize, int target){
if (nums == NULL || numsSize < 3) {
return 0;
}
int cnt = 0;
qsort(nums, numsSize, sizeof(int), comp);
for (int i = 0; i < numsSize - 2; ++i) {
for (int j = i + 1; j < numsSize - 1; ++j) {
int sum = target - nums[i] - nums[j];
int left = j + 1, right = numsSize - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= sum) {
right = mid - 1;
} else {
left = mid + 1;
}
}
cnt += (right - j);
}
}
return cnt;
}
C++
int threeSumSmaller(vector<int>& nums, int target) {
int cnt = 0;
int size = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < size - 2; ++i) {
for (int j = i + 1; j < size - 1; ++j) {
int sum = target - nums[i] - nums[j];
int left = j + 1, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= sum) {
right = mid - 1;
} else {
left = mid + 1;
}
}
cnt += (right - j);
}
}
return cnt;
}
Java
int threeSumSmaller(int[] nums, int target) {
int cnt = 0;
Arrays.sort(nums);
int size = nums.length;
for (int i = 0; i < size - 2; ++i) {
for (int j = i + 1; j < size - 1; ++j) {
int sum = target - nums[i] - nums[j];
int left = j + 1, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= sum) {
right = mid - 1;
} else {
left = mid + 1;
}
}
cnt += (right - j);
}
}
return cnt;
}
Python3
def threeSumSmaller(nums, target):
nums.sort()
cnt, size = 0, len(nums)
for i in range(len(nums) - 2):
for j in range(i + 1, size - 1):
sum = target - nums[i] - nums[j]
left, right = j + 1, size - 1
while left <= right:
mid = (right + left) // 2
if nums[mid] >= sum:
right = mid - 1
else:
left = mid + 1
cnt += (right - j)
return cnt
Golang
func threeSumSmaller(nums []int, target int) int {
if len(nums) < 3 {
return 0
}
cnt := 0
sort.Ints(nums)
for i := 0; i < len(nums) - 2; i++ {
for j := i + 1; j < len(nums) - 1; j++ {
sum := target - nums[i] - nums[j]
left, right := j + 1, len(nums) - 1
for left <= right {
mid := left + (right - left) / 2
if nums[mid] >= sum {
right = mid - 1
} else {
left = mid + 1
}
}
cnt = cnt + right - j
}
}
return cnt
}
时间复杂度:O(n^2lgn),其中 n 是数组的长度。
空间复杂度:O(1),未开辟额外存储空间。
遇到查找相关的题目,如果还是有序的,除了采用二分查找,还可以采用双指针中的对撞指针法去求解。
还是以 nums = [-2,0,1,3], target = 2 为例,如下图示。
示例
比较 nums[left] + nums[right] 与 target - nums[i] 的大小关系,进而缩小查找的范围;
查找方法
确定满足条件的三元组的对数。
确定结果
采用排序 + 对撞指针法完整查找过程,如下动图示:
排序 + 对撞指针法查找过程
C
int comp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int threeSumSmaller(int* nums, int numsSize, int target){
if (nums == NULL || numsSize < 3) {
return 0;
}
int cnt = 0;
qsort(nums, numsSize, sizeof(int), comp);
for (int i = 0; i < numsSize - 2; i++) {
int sum = target - nums[i];
int left = i + 1, right = numsSize - 1;
while (left < right) {
if (nums[left] + nums[right] < sum) {
cnt += (right - left);
left++;
} else {
right--;
}
}
}
return cnt;
}
C++
int threeSumSmaller(vector<int>& nums, int target) {
int cnt = 0;
int size = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < size - 2; ++i) {
int sum = target - nums[i];
int left = i + 1, right = size - 1;
while (left < right) {
if (nums[left] + nums[right] < sum) {
cnt += (right - left);
left++;
} else {
right--;
}
}
}
return cnt;
}
Java
int threeSumSmaller(int[] nums, int target) {
int cnt = 0;
Arrays.sort(nums);
int size = nums.length;
for (int i = 0; i < size - 2; ++i) {
int sum = target - nums[i];
int left = i + 1, right = size - 1;
while (left < right) {
if (nums[left] + nums[right] < sum) {
cnt += (right - left);
left++;
} else {
right--;
}
}
}
return cnt;
}
Python3
def threeSumSmaller(nums, target):
nums.sort()
cnt, size = 0, len(nums)
for i in range(len(nums) - 2):
sum = target - nums[i]
left, right = i + 1, size - 1;
while left < right:
if nums[left] + nums[right] < sum:
cnt += (right - left)
left += 1
else:
right -= 1
return cnt
Golang
func threeSumSmaller(nums []int, target int) int {
if len(nums) < 3 {
return 0
}
cnt := 0
sort.Ints(nums)
for i := 0; i < len(nums) - 2; i++ {
sum := target - nums[i]
left, right := i + 1, len(nums) - 1
for left < right {
if nums[left] + nums[right] < sum {
cnt += (right - left)
left += 1
} else {
right -= 1
}
}
}
return cnt
}
时间复杂度:O(n^2),其中 n 是数组的长度。
空间复杂度:O(1),未开辟额外存储空间。