本文共 1515 字，大约阅读时间需要 5 分钟。

LeetCode之两数之和

双重循环解法

这个问题要求我们找到数组中是否存在两个数，它们的和等于目标值。如果找到这两个数，就返回它们的下标。可以使用双重循环来实现这个任务。具体来说，我们可以通过遍历数组中的每一个元素，然后在后续的元素中寻找补足目标和的那个数。

但这种方法有一个缺点，就是当数组的长度较大时，这种解法的时间复杂度会很高。因为我们要遍历所有的两两组合，这在最坏情况下，时间复杂度是$n^2$，这虽然对于较小规模的数据还是可以接受的，但在大型数据集上表现会比较差。

哈希表解法

哈希表（或称为字典）可以将这个问题变得更加高效。这种方法的思路是先将数组中的每一个元素映射到它的下标。然后，对于每一个元素，我们可以检查是否存在能够与之组成目标和的数。如果已经存在这样的数，就直接返回这两个数的下标；否则，就将当前的数及其下标记录到哈希表中。

这种方法的时间复杂度是$O(n)$，因为我们只需要遍历数组两次：一次是插入数据，另一次是查找配对。这种效率显然高于双重循环法，它在大型数据集上的表现也会更优。

代码实现

public class TwoSum {    public static int[] twoSum1(int[] nums, int target) {        for (int i = 0; i < nums.length; i++) {            for (int j = i + 1; j < nums.length; j++) {                if (target - nums[i] == nums[j]) {                    return new int[]{i, j};                }            }        }        return null;    }    public static int[] twoSum2(int[] nums, int target) {        HashMap
   
     map = new HashMap<>();        for (int i = 0; i < nums.length; i++) {            int partnerNumber = target - nums[i];            if (map.containsKey(partnerNumber)) {                return new int[]{map.get(partnerNumber), i};            }            map.put(nums[i], i);        }        return null;    }    public static void main(String[] args) {        int[] nums = new int[]{2, 7, 11, 15};        int target = 22;        int[] myIndex = twoSum2(nums, target);        System.out.println(Arrays.toString(myIndex));    }}
   

注意事项：

• 在实际应用中，可能需要根据具体需求调整算法选择。对于非常小的数据集来说，双重循环法可能已经足够高效，甚至比哈希表法更易于实现。
• 如果预期数据集较大，或者频繁处理需要快速查找的场景，哈希表法显然是更好的选择。

转载地址：http://qihsz.baihongyu.com/