两个总和Java解决方案-DEV365 开发者社区

您好读者，让我们现在解决一个leetcode问题。

在此博客中，让我们解决Two Sum，它是Blind 75 List of LeetCode Problems。

两个总和是一个经典的编码挑战，也是LeetCode上的第一问题，它要求我们在数组中找到两个数字，加起来给定目标。

在这篇博客文章中，我们将探讨解决此问题的两种不同的方法：蛮力方法和最佳方法。我们将检查问题陈述，了解测试案例并深入研究两种方法的代码实现。此外，我们将分析每个溶液的时间和空间复杂性。

了解问题：

给定整数数组 nums 和一个目标整数 target ，任务是在数组中找到两个数字，以使它们的总和等于目标。
我们的目标是返回这两个数字的索引。
问题还提到，每个输入都将具有恰好，并且您不能两次使用 same element。 li>

了解测试用例：

要更好地理解问题，让我们考虑一些简单的测试用例：

测试案例1：

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

说明：索引0和1处的数字总和等于9。

的目标值。

测试案例2：

Input: nums = [3, 2, 4], target = 6
Output: [1, 2]

说明：指数1和2处的数字总和等于目标值6。

测试案例3：

Input: nums = [3, 3], target = 6
Output: [0, 1]

说明：索引0和1处的数字总和等于目标值6。

蛮力方法：嵌套环

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for(int i=0; i<nums.length; i++) {
            for(int j=i+1; j<nums.length; j++) {
                if((nums[i] + nums[j]) == target) {
                    result[0] = i;                    
                    result[1] = j;                    
                    return result;
                }
            }
        }
        return result;
    }
}

关键点：

我们浏览数组中的每个数字，然后将其添加到其他每个数字中，以查看其总和是否等于目标。
如果我们发现两个数字加利到目标，我们将返回其索引。

时间复杂性： o（n^2）

蛮力方法使用嵌套环检查每对数字，从而导致O（n^2）的时间复杂性，其中n是输入阵列的大小。

空间复杂性： o（1）

这种方法的空间复杂性是o（1），因为我们只需要固定大小 result 数组来存储索引。

最佳方法：hashmap

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++) {
            int numberToFind = target - nums[i];
            if(map.containsKey(numberToFind)) {
                result[0] = map.get(numberToFind); 
                result[1] = i;
            }
            map.put(nums[i], i);
        }
        return result;
    }
}