001_two_sum

 1 package algorithm;
 2 
 3 import java.util.Arrays;
 4 import java.util.HashMap;
 5 
 6 /**
 7  * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
 8  * <p>
 9  * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
10  * <p>
11  * 你可以按任意顺序返回答案。
12  */
13 public class Two_Sum001 {
14     /**
15      * 方法1：简单明了，暴力遍历
16      * 优点：简单、不伤脑
17      * 缺点：时间复杂度高O(n*n),在大数据集上，性能无法满足要求
18      *
19      * @param nums   数据集
20      * @param target 目标
21      * @return 满足条件的2个数据的下标
22      */
23     public static int[] twoSum(int[] nums, int target) {
24         int[] result = new int[2];
25         for (int i = 0; i < nums.length; i++) {
26             for (int j = 0; j < nums.length; j++) {
27                 if (target == nums[i] + nums[j] && i != j) {
28                     result[0] = i;
29                     result[1] = j;
30                     return result;
31                 }
32 
33             }
34         }
35         return result;
36 
37     }
38 
39     /**
40      * 方法2: 空间换时间
41      * 优点: 利用使用一个字典（哈希表）来优化查找的过程，将数字与其索引存储在字典中，提供了速度，节约了时间成本。总体时间复杂度为O(n)
42      * 缺点: nums数据集的数据会存储在字典中，占用内存,单时间复杂度降到了O(1)。企业实战时要考虑数据总量与服务器内存的情况。
43      *
44      * @param nums   数据集
45      * @param target 目标
46      * @return 满足条件的2个数据的下标
47      */
48     public static int[] twoSumV2(int[] nums, int target) {
49         HashMap<Integer, Integer> map = new HashMap<>();
50 
51         for (int i = 0; i < nums.length; i++) {
52 
53             int diff = target - nums[i];
54 
55             if (map.containsKey(diff)) {
56                 return new int[]{map.get(diff), i};
57             } else {
58                 map.put(nums[i], i);
59             }
60 
61 
62         }
63         return new int[0];
64 
65     }
66 
67     public static void main(String[] args) {
68         int[] nums = {2, 7, 11, 15};
69         int target = 9;
70         int[] result = twoSum(nums, target);
71         System.out.println(Arrays.toString(result));
72 
73         result = twoSumV2(nums, target);
74         System.out.println(Arrays.toString(result));
75     }
76 }

'''
方法1: 双层循环，暴力遍历
方法2: 空间换时间
'''


def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(len(nums)):
            if (i != j) and (nums[i] + nums[j] == target):
                return [i, j]

    return None


'''
方法2: 空间换实践。企业实战时要考虑整个数据量和内存情况
'''


def two_sumV2(nums, target):
    num_to_index_map = {}  # 创建一个字典来存储数字和其索引的对应关系,key为数字，value为其索引
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_to_index_map:
            return [num_to_index_map[complement], i]
        else:
            num_to_index_map[num] = i
    return None


# 示例用法
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(result)  # 输出: [0, 1]
two_sumV2(nums, target)
print(result)  # 输出: [0, 1]

// 方法1： 暴力2层遍历
function twoSum(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length; j++) {
          if (nums[i] + nums[j] === target  && i != j) {
            return [i,j];
          }
        }
    return [];
    }
}

// 方法2: 空间换时间
function twoSumV2(nums, target) {
    const numToIndex = new Map();  // 创建一个Map来存储数字和其索引的对应关系
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (numToIndex.has(complement)) {
            return [numToIndex.get(complement), i];
        }
        numToIndex.set(nums[i], i);
    }
    return [];
}

//  测试
let nums = [2, 7, 11, 15];
const target = 9;
let result = twoSum(nums, target);
console.log(result);  // 输出: [0, 1]

result = twoSumV2(nums, target);
console.log(result);  // 输出: [0, 1]