L38.【LeetCode题解】四数之和(双指针思想) 从汇编角度分析报错原因

目录

1.题目

2.分析

去重的代码

错误代码

3.完整代码

提交结果

---

1.题目

四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

• 1 <= nums.length <= 200
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

2.分析

本题和L37.【LeetCode题解】三数之和(双指针思想)题非常像,解法也是类似的,将原暴力解法的四重循环(循环变量为i,j,k,l)的最里面的两重循环换成双指针(left和right)即可

但题目条件限制"不重复的四元组",因此需要做去重操作,这个实现的思路在L37.【LeetCode题解】三数之和(双指针思想)文章中讲过了

去重的代码

i,j,left和right都要跳过相同的元素,一定要注意i,j,left,right不能超过各自的循环范围

left++;
while (nums[left]==nums[left-1]&&left<right)left++;right--;
while (nums[right]==nums[right+1]&&left<right)right--;j++;
while (nums[j]==nums[j-1]&&j<=nums.size()-3)j++;i++;
while (nums[i]==nums[i-1]&&i<=nums.size()-4)i++;

错误代码

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {if (nums.size()<4)return {};        sort(nums.begin(),nums.end());vector<vector<int>> ret;for (int i=0;i<=nums.size()-4;){for (int j=i+1;j<=nums.size()-3;){int left=j+1;int right=nums.size()-1;while (left<right){int sum=nums[i]+nums[j]+nums[left]+nums[right];if (sum>target)right--;else if (sum<target)left++;else//sum==target{ret.push_back({nums[i],nums[j],nums[left],nums[right]});left++;while (nums[left]==nums[left-1]&&left<right)left++;right--;while (nums[right]==nums[right+1]&&left<right)right--;}}j++;while (nums[j]==nums[j-1]&&j<=nums.size()-3)j++;}i++;while (nums[i]==nums[i-1]&&i<=nums.size()-4)i++;}return ret;}
};

报错信息:

sum超出int的存储范围,因为,sum最大可为

如果将int改成long long写成long long sum=nums[i]+nums[j]+nums[left]+nums[right];仍然会出错

明明已经用long long来扩大存储范围了却仍然会出错,想要找到具体原因需要看底层汇编代码的实现,查看Leetcode在线测试使用的编译器:

在What-are-the-environments-for-the-programming-languages找到了信息:

由于Leetcode的编译器为clang,可手动在Linux平台上测试,

先安装clang:

sudo apt update
sudo apt install clang

编译以下代码:

//保存为test.cpp
int  main()
{int i=1000000000;int j=1000000000;int left=1000000000;int right=1000000000;long long sum=i+j+left+right;return 0;
}

要看底层,需要看汇编代码,指令为:

clang -S test.cpp

 汇编代码为:

        .text.file   "test.cpp".globl  main                    # -- Begin function main.p2align        4, 0x90.type   main,@function
main:                                   # @main.cfi_startproc
# %bb.0:pushq   %rbp.cfi_def_cfa_offset 16.cfi_offset %rbp, -16movq    %rsp, %rbp.cfi_def_cfa_register %rbpxorl    %eax, %eaxmovl    $0, -4(%rbp)movl    $1000000000, -8(%rbp)   # imm = 0x3B9ACA00movl    $1000000000, -12(%rbp)  # imm = 0x3B9ACA00movl    $1000000000, -16(%rbp)  # imm = 0x3B9ACA00movl    $1000000000, -20(%rbp)  # imm = 0x3B9ACA00movl    -8(%rbp), %ecxaddl    -12(%rbp), %ecxaddl    -16(%rbp), %ecxaddl    -20(%rbp), %ecxmovslq  %ecx, %rdxmovq    %rdx, -32(%rbp)popq    %rbp.cfi_def_cfa %rsp, 8retq
.Lfunc_end0:.size   main, .Lfunc_end0-main.cfi_endproc# -- End function.ident  "clang version 10.0.0-4ubuntu1 ".section        ".note.GNU-stack","",@progbits.addrsig

只看重点部分:按照Intel汇编代码的风格来说,四个1000000000分别存到了[rbp-8],[rbp-12],[rbp-16],[rbp-20]的位置,之后使用3次addl指令,都做了相同的事,都是,而且都是由ecx寄存器来接收,ecx寄存器是4字节,由于int类型的最大值约为,因此在相加时会超过int类型的最大值,导致溢出,最后的movslq,作用为以符号扩展传送方式,将参数从4字节扩展为8字节,4字节是int类型,8字节是long long类型,会发生类型转换

注:movslq全称moves a 32-bit quantity (longword) into a 64-bit register (quadword) with sign extension 

因此可以理解为:long long sum=i+j+left+right;的i+j+left+right先按int类型相加,最后将结果的类型转换为long long

为了解决按int类型相加时产生的溢出,可以加两次:

long long sum=nums[i]+nums[j];
sum+=nums[left]+nums[right];

(原因:nums数组的元素不会超过,两个元素的和不会超过,比int类型的最大值要小)

或者只加一次,强制类型转换:

long long sum=nums[i]+nums[j]+(long long)(nums[left]+nums[right]);

注意:不能使用unsigned long long,数组元素值可为负

3.完整代码

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {if (nums.size()<4)return {};        sort(nums.begin(),nums.end());vector<vector<int>> ret;for (int i=0;i<=nums.size()-4;){for (int j=i+1;j<=nums.size()-3;){int left=j+1;int right=nums.size()-1;while (left<right){long long sum=nums[i]+nums[j];sum+=nums[left]+nums[right];if (sum>target)right--;else if (sum<target)left++;else//sum==target{ret.push_back({nums[i],nums[j],nums[left],nums[right]});left++;while (nums[left]==nums[left-1]&&left<right)left++;right--;while (nums[right]==nums[right+1]&&left<right)right--;}}j++;while (nums[j]==nums[j-1]&&j<=nums.size()-3)j++;}i++;while (nums[i]==nums[i-1]&&i<=nums.size()-4)i++;}return ret;}
};

提交结果