leetcode — 两数之和II_两数之和的所有组合

        给定一个无序数组和一个目标值，找出数组中两个数之和等于目标值的所有组合，并指出其时间复杂度。

例：数组arr = [3,5,3,5]，目标值是8。以结果是否可以重复为根本，分为3种情况。

1、可完全重复。结果为 [0, 1] [0, 3] [1, 2] [2,3]，共4种下标组合。

• 嵌套遍历。时间复杂度：O(n^2)。
• 哈希法。键存数组元素值，值存出现次数。时间复杂度：O(n)。
• 排序+双指针夹逼。时间复杂度：O(nlogn)。

2、半重复。结果为 [0, 1] [2,3]，或 [0, 3] [1, 2] ，共2种下标组合。

• 嵌套遍历。时间复杂度：O(n^2)。
• 哈希法。键存数组元素值，值存出现次数。时间复杂度：O(n)。
• 排序+双指针夹逼。时间复杂度：O(nlogn)。

3、不重复。结果为 [3,5]，共1种元素值组合。—— 对数组元素中的重复数字进行删除之后转换为无重复数字的两数之和的计算。

• 嵌套遍历。时间复杂度：O(n^2)。
• 哈希法。键存数组元素值，值不存。时间复杂度：O(n)。
• 排序+双指针夹逼。时间复杂度：O(nlogn)。
• 位图法。时间复杂度：O(目标值)。