【经典算法】LeetCode1:两数之和(Java/C/Python3实现含注释说明,Easy)

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

public int[] twoSum(int[] nums, int target) {
    int n = nums.length;
    for (int i = 0; i < nums.length; i++) { // 遍历数组，从第一个元素开始
        for (int j = i + 1; j < nums.length; j++) { // 在当前元素后面的元素中查找与目标值相加等于target的元素
            if (nums[i] + nums[j] == target) { // 如果找到了符合条件的元素对
                return new int[]{i, j}; // 返回这两个元素的下标
            }
        }
    }
    return new int[0]; // 如果没有找到符合条件的元素对，则返回空数组
}

#include <stdio.h>
#include <stdlib.h>
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* result = (int*)malloc(2 * sizeof(int)); // 分配保存结果的内存空间
    *returnSize = 0; // 初始化返回结果数组的大小为0，表示没有找到满足条件的元素对
    
    for (int i = 0; i < numsSize; i++) { // 外层循环遍历数组中的每个元素
        for (int j = i + 1; j < numsSize; j++) { // 内层循环遍历当前元素后面的每个元素
            if (nums[i] + nums[j] == target) { // 检查两个元素的和是否等于目标值
                result[0] = i; // 将符合条件的第一个元素的下标存入结果数组的第一个位置
                result[1] = j; // 将符合条件的第二个元素的下标存入结果数组的第二个位置
                *returnSize = 2; // 更新返回结果数组的大小为2
                return result; // 返回结果数组
            }
        }
    }
    
    return result; // 返回结果数组，如果没有找到满足条件的元素对，数组中的元素值均为0
    
    // 注意：需要在适当的时候释放result指向的动态分配内存，以避免内存泄漏
}

from typing import List
def twoSum(nums: List[int], target: int) -> List[int]:
    result = [] # 用于存储结果的列表
    n = len(nums)
    
    for i in range(n): # 外层循环遍历列表中的每个元素
        for j in range(i+1, n): # 内层循环遍历当前元素后面的每个元素
            if nums[i] + nums[j] == target: # 检查两个元素的和是否等于目标值
                result.append(i) # 将符合条件的第一个元素的下标添加到结果列表中
                result.append(j) # 将符合条件的第二个元素的下标添加到结果列表中
                return result # 返回结果列表
    
    return result # 如果没有找到满足条件的元素对，返回空列表

import java.util.HashMap;
class Solution {
    public int[] twoSum(int[] nums, int target) {
        //key为当前值，value为当前值的位置
        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}; // 返回HashMap中保存的差值元素的下标和当前元素的下标
            }
            map.put(nums[i], i); // 将当前元素添加到HashMap中
        }
        return new int[0]; // 如果没有找到满足条件的元素对，返回空数组
    }
}

#include <stdio.h>
#include <stdlib.h>
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* result = (int*)malloc(2 * sizeof(int));
    *returnSize = 0;
    
    // 创建哈希表
    int hashtable[20001] = {0};
    
    for (int i = 0; i < numsSize; ++i) {
        int complement = target - nums[i]; // 计算差值，即目标值与当前元素的差值
        
        // 检查哈希表中是否存在差值
        if (complement >= -10000 && complement <= 10000 && hashtable[complement + 10000] != 0) {
            result[0] = hashtable[complement + 10000] - 1; // 返回哈希表中保存的差值元素的下标
            result[1] = i; // 返回当前元素的下标
            *returnSize = 2; // 更新返回结果数组的大小为2
            return result;
        }
        
        // 将当前元素添加到哈希表中
        hashtable[nums[i] + 10000] = i + 1;
    }
    
    return result;
}

from typing import List
from collections import defaultdict
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = defaultdict(int) # 使用defaultdict来容纳哈希表
        for i in range(len(nums)):
            complement = target - nums[i] # 计算差值，即目标值与当前元素的差值
            if complement in hashtable:
                return [hashtable[complement], i] # 返回哈希表中保存的差值元素的下标和当前元素的下标
            hashtable[nums[i]] = i # 将当前元素添加到哈希表中
        
        return [] # 如果没有找到满足条件的元素对，返回空列表

import java.util.Arrays;
public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        // 对数组进行排序
        Arrays.sort(nums);
        
        // 初始化左右指针
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            // 计算当前左右指针对应元素之和
            int sum = nums[left] + nums[right];
            
            if (sum == target) {
                // 找到目标值，返回对应的数组下标
                return new int[]{left, right};
            } else if (sum < target) {
                // sum小于目标值，将左指针向右移动一位
                left++;
            } else {
                // sum大于目标值，将右指针向左移动一位
                right--;
            }
        }
        
        // 没有找到满足条件的两个数，返回空数组
        return new int[]{};
    }
}

#include <stdio.h>
#include <stdlib.h>
int* twoSum(int* nums, int numsSize, int target) {
    // 对数组进行排序（可以使用快速排序等）
    qsort(nums, numsSize, sizeof(int), compare);
    
    // 初始化左右指针
    int left = 0;
    int right = numsSize - 1;
    
    while (left < right) {
        // 当前左右指针对应元素之和
        int sum = nums[left] + nums[right];
        
        if (sum == target) {
            // 找到目标值，返回对应的数组下标
            int* result = (int*)malloc(2 * sizeof(int));
            result[0] = left;
            result[1] = right;
            return result;
        } else if (sum < target) {
            // sum小于目标值，将左指针向右移动一位
            left++;
        } else {
            // sum大于目标值，将右指针向左移动一位
            right--;
        }
    }
    
    // 没有找到满足条件的两个数，返回空数组
    return NULL;
}
int compare(const void* a, const void* b) {
    // 用于qsort排序的比较函数
    return (*(int*)a - *(int*)b);
}

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 对数组进行排序
        nums.sort()
        
        left = 0  # 左指针
        right = len(nums) - 1  # 右指针
        
        while left < right:
            # 当前左右指针对应元素之和
            sum = nums[left] + nums[right]
            
            if sum == target:
                # 找到目标值，返回对应的数组下标
                return [left, right]
            elif sum < target:
                # sum小于目标值，将左指针向右移动一位
                left += 1
            else:
                # sum大于目标值，将右指针向左移动一位
                right -= 1
        
        # 没有找到满足条件的两个数，返回空数组
        return []