LeetCode算法题---两数之和（一）

柔情只为你懂 2023-10-12 19:08 37阅读 0赞

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

示例 1：

输入：nums = [2,7,11,15], target = 9 
    输出：[0,1] 
    解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6 
    输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6 
    输出：[0,1]

解题代码：

class Solution {
        public int[] twoSum(int[] nums, int target) {
           int[] newNums = Arrays.copyOf(nums, nums.length);
            Arrays.sort(newNums);
            int left = 0;
            int right = newNums.length - 1;
            while (left < right) {
                int sum = newNums[left] + newNums[right];
                if (sum > target) {
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    break;
                }
            }
            int index1 = -1;
            int index2 = -1;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == newNums[left] && index1 == -1) {
                    index1 = i;
                } else if (nums[i] == newNums[right] && index2 == -1) {
                    index2 = i;
                }
                if (index1 != -1 && index2 != -1) {
                    break;
                }
            }
            return new int[] {index1, index2};
        }
    }

解题思路：

这是一个 Java 实现的两数之和问题的解法。下面是每一段的具体解释：

public int[] twoSum(int[] nums, int target) {

这是一个公共方法 twoSum，它接收两个参数： nums 表示需要进行计算的整数数组，target 表示需要满足的条件，即两数之和等于 target。方法返回一个包含两个值的整数数组，这两个值分别是相加等于目标值的两个数在原数组中的下标。

int[] newNums = Arrays.copyOf(nums, nums.length);

将原始数组 nums 复制到新的数组 newNums。

Arrays.sort(newNums);

对新数组 newNums 进行排序。

int left = 0; int right = newNums.length - 1;

定义两个指针 left 和 right，它们分别指向排序后的数组 newNums 的最左侧和最右侧。

while (left < right) { int sum = newNums[left] + newNums[right]; if (sum > target) { right--; } else if (sum < target) { left++; } else { break; } }

在数组 newNums 上执行双指针循环。根据指针指向的两个元素之和与目标值 target 的比较情况，调整指针的位置，直到满足条件（两数之和等于目标值），或者指针重合（没有找到答案）。

int index1 = -1; int index2 = -1; for (int i = 0; i < nums.length; i++) { if (nums[i] == newNums[left] && index1 == -1) { index1 = i; } else if (nums[i] == newNums[right] && index2 == -1) { index2 = i; } if (index1 != -1 && index2 != -1) { break; } }

根据有序数组 newNums 的结果，遍历原始数组 nums，找到相加等于目标值的两个值在原数组中的下标。

return new int[] {index1, index2};

将两个下标封装到一个新的数组中并返回。