C#查找数组中和为目标值的元素下标，求贪心/动态规划解法

你描述的是经典的两数之和问题，首先先纠正一个认知误区：这个场景下贪心和动态规划并不是最优选择，甚至会额外增加实现复杂度，工业界通用的最优解是基于哈希字典的单次遍历方案，时间复杂度O(n)，比你之前用的双层循环O(n²)效率高很多，代码也更简洁。

为什么不推荐用贪心/动态规划解决该问题 #

• 贪心算法要求问题满足贪心选择性质，也就是每一步选局部最优就能得到全局最优，但两数之和需要组合两个独立元素，没有明确的局部最优选择策略，强行用贪心需要先排序，会破坏原数组的下标对应关系，额外需要存储下标映射，反而更麻烦
• 动态规划适合解决多阶段决策、存在重叠子问题和最优子结构的问题，比如求最多/最少组合数，单纯找两个数的下标用DP会额外浪费空间存储中间状态，完全没有必要

最优实现方案（哈希字典法） #

思路很简单：遍历数组的时候，用字典存已经遍历过的元素值和对应的下标，每遍历到一个新元素，就计算目标值和当前元素的差值，判断差值是否已经在字典里存在，如果存在就直接返回对应的两个下标即可。

示例代码 #

using System;
using System.Collections.Generic;

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> numMap = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];
            if (numMap.ContainsKey(complement)) {
                return new int[] { numMap[complement], i };
            }
            // 避免同一个元素被重复使用，判断后再存入字典
            if (!numMap.ContainsKey(nums[i])) {
                numMap.Add(nums[i], i);
            }
        }
        // 没有符合条件的组合返回空数组，也可以根据需求抛异常
        return Array.Empty<int>();
    }
}

调用测试 #

// 测试用例
int[] a = {4, 3, 8, 1};
int target = 5;
Solution sol = new Solution();
int[] result = sol.TwoSum(a, target);
// 输出结果：[0,3]
Console.WriteLine($"[{string.Join(",", result)}]");

扩展场景说明 #

如果你的需求后续要扩展为任意多个元素求和等于目标值或者求所有符合条件的组合数，可以再考虑动态规划方案，单纯两数场景用哈希法是最优选择。

内容的提问来源于stack exchange，提问作者VA1267