谷歌高频面试题-较小的三数之和
前言
大家好，我是熊哥。
今天给大家带来一道与数组相关的高频面试题，这道题被IBM、谷歌和高盛等互联网大厂作为面试题考过，即力扣上的第 259 题-较小的三数之和和领扣上的第 918 题-三数之和小于。
本文主要介绍排序 + 二分查找和排序 + 对撞指针等三种方法来解答此题，供大家参考，希望对大家有所帮助。
较小的三数之和
给定一个长度为 n 的整数数组和一个目标值 target，寻找能够使条件
nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k
个数（0 <= i < j < k < n）。
示例及进阶
解题思路
本题很容易想到通过暴力枚举去做。
解法一：暴力法
按照题目的意思，遍历（三次）整个数组，找出满足条件的解即可。
Show me the Code
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]的大小关系，缩短查找区间；
缩小查找范围
然后再确定满足条件的三元组的对数。
确定合适的三元组的对数
采用排序 + 二分查找法，完整查找过程，如下动图示：
查找过程（排序 + 二分法）
Show me the Code
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] 的大小关系，进而缩小查找的范围；
查找方法
确定满足条件的三元组的对数。
确定结果
采用排序 + 对撞指针法完整查找过程，如下动图示：
排序 + 对撞指针法查找过程
Show me the Code
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)，未开辟额外存储空间。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-11-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录