一、问题理解与初步分析

首先，让我们仔细分析一下这个问题。我们需要在一个整数数组中找到两个数，使它们的和等于给定的目标值，并返回这两个数的数组下标。

给定的条件很明确：

• 每种输入只会对应一个答案
• 不能使用相同的元素两次
• 可以按任意顺序返回答案

通过示例，我可以更清楚地理解问题：

• 示例1：nums = [2,7,11,15], target = 9，输出应为[0,1]，因为2+7=9
• 示例2：nums = [3,2,4], target = 6，输出应为[1,2]，因为2+4=6
• 示例3：nums = [3,3], target = 6，输出应为[0,1]，因为3+3=6

问题本质上是要找到两个下标i和j，使得nums[i] + nums[j] = target。

初步思考

对于这个问题，我的第一反应是使用最直接的方法：遍历数组中的每一对数字，检查它们的和是否等于目标值。这是一个暴力解法，让我们看看如何实现它。

// 暴力解法的初步思路
public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[] {i, j};
            }
        }
    }
    // 根据题目条件，肯定有解，所以不会执行到这里
    return null;
}

这个解法的思路很直观：使用两层循环遍历数组中的所有可能的数字对。外层循环选择第一个数，内层循环选择第二个数，然后检查它们的和是否等于目标值。

时间复杂度分析：外层循环执行n次，内层循环平均执行(n-1)/2次，所以总体时间复杂度为O(n²)。

空间复杂度分析：只使用了常数级别的额外空间，所以空间复杂度为O(1)。

二、暴力解法的实现与优化思考

让我们先实现这个暴力解法，看看它的具体执行过程。

public int[] twoSum(int[] nums, int target) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[] {i, j};
            }
        }
    }
    return new int[] {}; // 假设始终有解，所以不会执行到这里
}

让我们用示例1来验证一下这个解法：
nums = [2,7,11,15], target = 9

1. i = 0, nums[0] = 2
   • j = 1, nums[1] = 7, 2 + 7 = 9 == target，返回[0, 1]

这个解法确实可以工作，但时间复杂度为O(n²)，当数组很大时效率会很低。题目的进阶要求是找出时间复杂度小于O(n²)的算法，所以我们需要思考如何优化。

优化思路的诞生

在暴力解法中，对于每个nums[i]，我们都要检查是否存在一个nums[j]使得nums[i] + nums[j] = target，即nums[j] = target - nums[i]。这个过程本质上是在数组中查找特定值，而查找操作如果使用线性遍历，时间复杂度就是O(n)。

这让我想到，如果我们能够更快地查找target - nums[i]是否存在于数组中，就可以提高算法效率。哈希表是一种能够在平均O(1)时间内进行查找的数据结构，所以我们可以考虑使用哈希表来优化查找过程。

具体来说，我们可以创建一个哈希表，将数组元素的值作为键，下标作为值存储在哈希表中。然后，对于每个nums[i]，我们检查target - nums[i]是否在哈希表中。如果在，就找到了符合条件的两个数。

但这里有一个问题：如果我们先构建完整的哈希表，然后再进行查找，可能会使用同一个元素两次。例如，如果nums = [3,3], target = 6，将整个数组放入哈希表后，键3对应的值会被更新为1（后一个3的下标），查找时会返回[0,1]，但这实际上使用了同一个元素两次。

经过思考，我发现可以一边遍历数组，一边更新哈希表，同时进行查找。这样，当我们处理到nums[i]时，哈希表中只包含前i-1个元素，保证了不会使用同一个元素两次。

三、基于哈希表的优化解法

基于以上思考，我们可以使用哈希表来优化查找过程，将时间复杂度降低到O(n)。

具体实现思路如下：

1. 创建一个空的哈希表
2. 遍历数组nums，对于每个元素nums[i]：
   a. 计算补数complement = target - nums[i]
   b. 查找complement是否在哈希表中
   c. 如果在，返回当前元素的下标i和哈希表中complement对应的下标
   d. 如果不在，将当前元素nums[i]和它的下标i存入哈希表

让我开始实现这个解法：

public int[] twoSum(int[] nums, int target) {
    // 创建哈希表，用于存储数组元素及其下标
    Map<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);
    }
    
    // 假设始终有解，所以不会执行到这里
    return new int[] {};
}

让我用示例1再次验证这个解法：
nums = [2,7,11,15], target = 9

1. i = 0, nums[0] = 2, complement = 9 - 2 = 7
   • map为空，不包含7
   • 将(2, 0)存入map，现在map = {2=0}
2. i = 1, nums[1] = 7, complement = 9 - 7 = 2
   • map包含2，对应的下标是0
   • 返回[0, 1]

这个解法确实可以正确找到解，而且时间复杂度降低到了O(n)，因为我们只需遍历一次数组，哈希表的查找操作平均时间复杂度为O(1)。

空间复杂度方面，我们使用了一个哈希表来存储数组元素及其下标，最坏情况下需要存储n-1个元素（最后一个元素找到解），所以空间复杂度为O(n)。

四、最终解法的细化与完整实现

在实现基于哈希表的解法时，我注意到一个小细节：我们在返回结果时，顺序是[map.get(complement), i]，这确保了返回的结果是按照数组中的顺序排列的，即较小下标在前。这不是必须的，因为题目允许按任意顺序返回答案，但这是一个很自然的选择。

让我们再仔细检查一下这个解法，确保没有任何遗漏或错误：

public int[] twoSum(int[] nums, int target) {
    // 创建哈希表，用于存储数组元素及其下标
    Map<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);
    }
    
    // 假设始终有解，所以不会执行到这里
    return new int[] {};
}

等等，我看到一个问题。在上面的代码中，我们返回的顺序是[map.get(complement), i]，这假设了哈希表中存储的元素的下标小于当前遍历到的元素的下标。但实际上，这种假设不一定成立。

让我重新考虑一下返回顺序的问题。根据题目描述，我们可以按任意顺序返回答案，所以实际上我们可以返回[i, map.get(complement)]或[map.get(complement), i]，取决于哪种方式更方便或更符合逻辑。

考虑到我们的解法是从前往后遍历数组，当找到complement在哈希表中时，complement对应的下标一定小于当前的下标i（因为我们是在遍历到i之前将之前的元素存入哈希表的）。所以，如果我们想按照数组的顺序返回结果，应该返回[map.get(complement), i]。

不过，在这个问题中，返回顺序不影响解的正确性，所以最终的解法可以是：

public int[] twoSum(int[] nums, int target) {
    Map<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);
    }
    return new int[] {};
}

这个解法的时间复杂度为O(n)，空间复杂度为O(n)，满足进阶要求的时间复杂度小于O(n²)。

让我们再次用示例验证这个解法：

示例1：nums = [2,7,11,15], target = 9

1. i = 0, nums[0] = 2, complement = 7
   • map为空，不包含7
   • 将(2, 0)存入map
2. i = 1, nums[1] = 7, complement = 2
   • map包含2，对应的下标是0
   • 返回[0, 1]

示例2：nums = [3,2,4], target = 6

1. i = 0, nums[0] = 3, complement = 3
   • map为空，不包含3
   • 将(3, 0)存入map
2. i = 1, nums[1] = 2, complement = 4
   • map不包含4
   • 将(2, 1)存入map
3. i = 2, nums[2] = 4, complement = 2
   • map包含2，对应的下标是1
   • 返回[1, 2]

示例3：nums = [3,3], target = 6

1. i = 0, nums[0] = 3, complement = 3
   • map为空，不包含3
   • 将(3, 0)存入map
2. i = 1, nums[1] = 3, complement = 3
   • map包含3，对应的下标是0
   • 返回[0, 1]

所有示例都验证通过，确认这个解法是正确的。

完整代码

最终的完整Java代码如下：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<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);
        }
        return new int[] {0, 0}; // 根据题目条件，肯定有解，这行代码不会执行
    }
}

这个解法利用哈希表将查找时间从O(n)降低到O(1)，使得整体算法的时间复杂度从暴力解法的O(n²)降低到O(n)，满足了进阶要求。同时，它使用了O(n)的额外空间来存储哈希表，这是一个典型的空间换时间的优化策略。

这个问题的解决过程体现了一个重要的编程思想：通过合适的数据结构，可以显著提高算法的效率。在这个例子中，哈希表的使用让我们能够在O(1)时间内查找特定值，从而将整体时间复杂度降低到O(n)。