本文共 4519 字，大约阅读时间需要 15 分钟。

解题思路与实现总结

LeetCode1. 两数之和

问题描述： 找出两数之和等于目标值的下标对。

解决方案分析：

• 暴力模拟法： 简单暴力解法，适用于小规模数据，但效率较低。
• 哈希表优化法： 使用哈希表（字典）存储元素及其索引。遍历数组时，快速查找目标值与当前元素之和的补丁是否存在，如果存在返回对应的索引对。这种方法的时间复杂度为 O(N log N)，因为每个元素的插入、查询操作都需要 O(log N) 时间。

优化点：

• 使用哈希表避免了嵌套循环的时间复杂度问题。
• map 的 key 是数组中的值，value 是对应的索引。遍历数组时，判断是否存在目标值与当前值之和的补丁。

实现代码：

#include 
   
    #include 
    
     using namespace std;class Solution {public:    vector
     
       twoSum(vector
      
        nums, int target) {        unordered_map
       
         m;        vector
        
          ans; for (int i = 0; i < nums.size(); ++i) { if (m.count(target - nums[i])) { ans.push_back(m[target - nums[i]]); ans.push_back(i); break; } m[nums[i]] = i; } return ans; }};
        
       
      
     
    
   

LeetCode3. 三数之和

问题描述： 找出三数之和等于目标值的三元组。

解决方案分析：

优化点：

• 排序数组后，双指针法的时间复杂度为 O(N log N)。
• 去除重复解的方法是记录已经加入结果中的三元组，避免重复计数。

实现代码（排序后双指针法）：

#include 
   
    #include 
    
     using namespace std;class Solution {public:    vector
     
      
       > threeSum(vector
       
         nums) {        vector
        
         
          > ans; if (nums.size() < 3) return ans; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); ++i) { if (nums[i] > 0) continue; //剪枝条件 int left = i + 1; int right = nums.size() - 1; while (left < right) { long long sum = (long long)nums[i] + nums[left] + nums[right]; if (sum == 0) { ans.push_back({nums[i], nums[left], nums[right]}); //去重处理：如果当前三个元素与前一个相同，则跳过 while (left < right && nums[left] == nums[left - 1]) ++left; while (left < right && nums[right] == nums[right - 1]) --right; } else if (sum < 0) { ++left; } else { --right; } } } return ans; }};
         
        
       
      
     
    
   

LeetCode16. 最接近的三数之和

问题描述： 找出最接近目标值的三个数之和。

优化点：

• 減少比较操作通过绝对值判断优化性能。
• 排序后保证有序性，避免重复计算。

实现代码：

#include 
   
    #include 
    
     using namespace std;class Solution {public:    int threeSumClosest(vector
     
       nums, int target) {        sort(nums.begin(), nums.end());        int closeNum = nums[0] + nums[1] + nums[2];        int bestDiff = INT_MAX;        for (int i = 0; i < nums.size(); ++i) {            int left = i + 1;            int right = nums.size() - 1;            while (left < right) {                long long sum = nums[i] + nums[left] + nums[right];                int diff = abs((int)(sum) - target);                if (diff < bestDiff) {                    bestDiff = diff;                    closeNum = sum;                }                if (sum < target) {                    ++left;                } else if (sum > target) {                    --right;                } else {                    break;                }            }        }        return (int)closeNum;    }};
     
    
   

LeetCode18. 四数之和

问题描述： 找出四个数之和等于目标值的四元组。

优化点：

• 初始排除三个及以上相同元素的 fused纸条元组。
• 在四数之和的情况下，需要双层循环来处理溶液选择，优化搜索空间。

实现代码：

#include 
   
    #include 
    
     using namespace std;class Solution {public:    vector
     
       fourSum(vector
      
        nums, int target) {        sort(nums.begin(), nums.end());        vector
       
         result;        int size = nums.size();        for (int a = 0; a < size; ++a) {            if (a > 0 && nums[a] == nums[a - 1]) continue; //去重            for (int b = a + 1; b < size; ++b) {                if (b > a + 1 && nums[b] == nums[b - 1]) continue; //去重                int i = b + 1;                int j = size - 1;                while (i < j) {                    long long sum = nums[a] + nums[b] + nums[i] + nums[j];                    if (sum < target) {                        ++i; //为了得到更小的和，尝试更大的数                    } else if (sum > target) {                        --j; //为了得到更小的和，尝试更小的数                    } else {                        result.push_back({nums[a], nums[b], nums[i], nums[j]});                        //去重处理：判断是否有重复的解                        while (i < j && nums[i] == nums[i - 1]) ++i;                        while (i < j && nums[j] == nums[j - 1]) --j;                    }                }            }        }        return result;    }};
       
      
     
    
   

总结

以上内容包括了多个经典算法问题的解法和优化思路，涵盖了双指针法、哈希表优化、剪枝技巧等内容。这些方法通过排序和双指针缩小搜索空间，保证了算法在较大数据集上的性能。每个问题都有具体的解决方案和优化解释，适合参考和实践。