深度解析:探索「两数之和」问题的多种算法解决方案

2023-12-14 19:59:15

今天要讨论的是「两数之和」问题,并将从哈希表解法到排序数组与双指针法、再到一遍哈希表解法的不同解决方案进行详细探讨

哈希表解法:

第一,使用了一种简单而有效的方法——哈希表。我们创建了一个 HashMap,用于存储已遍历过的元素及其索引。通过遍历数组,我们计算目标值与当前元素的差值,并检查哈希表中是否存在这个差值。如果存在,则返回这两个数的索引。这个方法时间复杂度为 O(n),空间复杂度为 O(n)。

// 哈希表解法
import java.util.HashMap;

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        // 创建一个 HashMap 用于存储已经遍历过的元素及其索引
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 计算目标值与当前元素的差值
            int complement = target - nums[i];
            
            // 检查哈希表中是否存在差值,如果存在则返回两个数的索引
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            
            // 将当前元素及其索引存入哈希表
            map.put(nums[i], i);
        }
        
        // 如果没有找到符合条件的两个数,抛出异常
        throw new IllegalArgumentException("No two sum solution");
    }
}

排序数组与双指针法:

第二,利用了排序数组和双指针法。首先对数组进行排序,然后使用左右指针来查找两个数的和是否等于目标值。排序后的数组为双指针法提供了更多信息,使得查找过程更高效。这个方法时间复杂度为 O(nlogn),但是空间复杂度仅为 O(1),因为排序操作是原地进行的。

// 排序数组与双指针法
import java.util.Arrays;

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        // 对数组进行排序,创建排序后的数组副本
        int[] sortedNums = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sortedNums);
        
        // 初始化左右指针
        int left = 0, right = nums.length - 1;

        // 使用双指针查找两数之和等于目标值
        while (left < right) {
            int sum = sortedNums[left] + sortedNums[right];
            if (sum == target) {
                int index1 = -1, index2 = -1;
                for (int i = 0; i < nums.length; i++) {
                    if (nums[i] == sortedNums[left] && index1 == -1) {
                        index1 = i;
                    } else if (nums[i] == sortedNums[right] && index2 == -1) {
                        index2 = i;
                    }
                }
                return new int[]{Math.min(index1, index2), Math.max(index1, index2)};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        // 如果没有找到符合条件的两个数,抛出异常
        throw new IllegalArgumentException("No two sum solution");
    }
}

一遍哈希表解法:

最后,我们探讨了更高效的算法,利用了哈希表实现一遍扫描完成。这种方法只需要一次遍历,使用哈希表来存储已遍历过的数字及其索引,因此可以在更短的时间内解决问题。时间复杂度为 O(n),空间复杂度也为 O(n)。

// 一遍哈希表解法
import java.util.HashMap;

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        // 创建一个 HashMap 用于存储已经遍历过的元素及其索引
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 计算目标值与当前元素的差值
            int complement = target - nums[i];
            
            // 检查哈希表中是否存在差值,如果存在则返回两个数的索引
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            
            // 将当前元素及其索引存入哈希表
            map.put(nums[i], i);
        }
        
        // 如果没有找到符合条件的两个数,抛出异常
        throw new IllegalArgumentException("No two sum solution");
    }
}

这些方法各有优劣,但都是帮助我们更好理解和运用算法的绝佳实践!希望这份分享能够帮助到你。

文章来源:https://blog.csdn.net/qq_45476500/article/details/112373337
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。