刷题总结——多数相加（减）等于特定值

概述

• 存在一类题目，给你一些数组（可能是一个，也可能是多个），给你一个target，要求你从给定的数据中，选择一些数相加（减）等于target

思路

• 这类算是排列组合题。如果暴力求解，就直接多重循环将数字排列组合验证即可(一般会超时)
• 但是考虑到已知target,我们可以先排列组合部分获得值，然后根据结果去找接下来需要应该要获得的值
• 重点就是如何确定数据中是否存在应该要获得的值
  • 一种情况，可以利用find()函数
    • STL find()时间复杂度是O(n)
    • map、set成员函数find()是O(logn)
  • 另一种情况，可以利用哈希，空间换时间，缩小时间复杂度
    • 先将排列组合的值保存下来，减少循环层数
• 此类题目可能存在的不同要求：
  1. 最终结果获得的值不能重复：那么在找的过程中，要确保找到的数字是之前部分结果中没有使用过的，此时哈希法不太好用，可以考虑多指针法
     • 多指针法，一般要对数据进行排序，所以也不适用需要最后返回索引的问题

题目分析

同一集合中找数据+返回数据索引

• [1.Two Sum](LeetCode 1.md/)

同一集合中找数据+返回结果数值

• [15.3Sum](LeetCode 15.md)
• 18.4Sum

不同集合中找数据+返回结果数量

• 454.4Sum II