leetcode第16题

简介: 受到上一题的启发,没有看的,推荐大家可以看一下。我们完全可以先将数组排序,然后先固定一个数字,然后利用头尾两个指针进行遍历,降低一个 O(n)的时间复杂度。如果 sum 大于 target 就减小右指针,反之,就增加左指针。

image.png

top16

上一道题很类似,只不过这个是给一个目标值,找三个数,使得他们的和最接近目标值。

解法一 暴力解法

遍历所有的情况,然后求出三个数的和,和目标值进行比较,选取差值最小的即可。本以为时间复杂度太大了,神奇的是,竟然 AC 了。

publicintthreeSumClosest(int[] nums, inttarget) {
intsub=Integer.MAX_VALUE; //保存和 target 的差值intsum=0; //保存当前最接近 target 的三个数的和for (inti=0; i<nums.length; i++) {
for (intj=i+1; j<nums.length; j++)
for (intk=j+1; k<nums.length; k++) {
if (Math.abs((nums[i] +nums[j] +nums[k] -target)) <sub) {
sum=nums[i] +nums[j] +nums[k];
sub=Math.abs(sum-target);
                }
            }
    }
returnsum;
}

时间复杂度:O(n³),三层循环。

空间复杂度:O(1),常数个。

解法二

受到上一题的启发,没有看的,推荐大家可以看一下。我们完全可以先将数组排序,然后先固定一个数字,然后利用头尾两个指针进行遍历,降低一个 O(n)的时间复杂度。

如果 sum 大于 target 就减小右指针,反之,就增加左指针。

publicintthreeSumClosest(int[] nums, inttarget) {
Arrays.sort(nums);
intsub=Integer.MAX_VALUE;
intsum=0;
for(inti=0;i<nums.length;i++){ 
intlo=i+1,hi=nums.length-1;
while(lo<hi){
if(Math.abs((nums[lo]+nums[hi]+nums[i]-target))<sub){
sum=nums[lo]+nums[hi]+nums[i];
sub=Math.abs(sum-target);
            }
if(nums[lo]+nums[hi]+nums[i]>target){
hi--;
            }else{
lo++;
            }
        }
    }
returnsum;
}

时间复杂度:如果是快速排序的 O(log_n)O(logn) 再加上 O(n²),所以就是 O(n²)。

空间复杂度:O(1)。

和上一道题非常非常的相似了,先对数组排序,然后利用两头的指针,可以说是十分的优雅了。


目录
打赏
0
0
0
0
10
分享
相关文章
|
9月前
leetcode-1518:换酒问题
leetcode-1518:换酒问题
44 0
|
9月前
|
leetcode-283:移动零
leetcode-283:移动零
32 0
|
9月前
LeetCode
LeetCode
47 0
|
9月前
leetcode-827:最大人工岛
leetcode-827:最大人工岛
78 0
leetcode 827 最大人工岛
leetcode 827 最大人工岛
69 0
leetcode 827 最大人工岛
leetcode第38题
难在了题目是什么意思呢? 初始值第一行是 1。 第二行读第一行,1 个 1,去掉个字,所以第二行就是 11。 第三行读第二行,2 个 1,去掉个字,所以第三行就是 21。 第四行读第三行,1 个 2,1 个 1,去掉所有个字,所以第四行就是 1211。 第五行读第四行,1 个 1,1 个 2,2 个 1,去掉所有个字,所以第五航就是 111221。 第六行读第五行,3 个 1,2 个 2,1 个 1,去掉所以个字,所以第六行就是 312
leetcode第38题
leetcode第34题
第二种思路,参考这里。 我们开始更新 start 的时候,是 mid + 1,如果剩两个元素,例如 2 4,target = 6 的话,此时 mid = 0,start = mid + 1 = 1,我们返回 start + 1 = 2。如果 mid 是右端点,那么 mid = 1,start = mid + 1 = 2,这样就可以直接返回 start 了,不需要在返回的时候加 1 了。
122 0
leetcode第34题
leetcode第45题
时间复杂度:O(n)。 空间复杂度:O(1)。 这里要注意一个细节,就是 for 循环中,i < nums.length - 1,少了末尾。因为开始的时候边界是第 0 个位置,steps 已经加 1 了。如下图,如果最后一步刚好跳到了末尾,此时 steps 其实不用加 1 了。如果是 i < nums.length,i 遍历到最后的时候,会进入 if 语句中,steps 会多加 1 。
134 0
leetcode第45题
leetcode第42题
也就是红色区域中的水, 数组是 height = [ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 ] 。 原则是高度小于 2,temp ++,高度大于等于 2,ans = ans + temp,temp = 0。 temp 初始化为 0 ,ans 此时等于 2。 height [ 0 ] 等于 0 < 2,不更新。 height [ 1 ] 等于 1 < 2,不更新。 height [ 2 ] 等于 0 < 2, 不更新。 height [ 3 ] 等于 2 >= 2, 开始更新 height [ 4 ] 等于 1 < 2,temp = temp + 1 = 1。 h
118 0
leetcode第42题
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等