LintCode—两数之和&落单的数
Skyen Lv4
 2020-10-15 15:30:16    

题目要求

56. 两数之和

给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。

你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。

样例
Example1:
给出 numbers = [2, 7, 11, 15], target = 9, 返回 [0, 1].
Example2:
给出 numbers = [15, 2, 7, 11], target = 9, 返回 [1, 2].
挑战
给自己加点挑战

O(n)O(n) 空间复杂度，O(nlogn)O(nlogn) 时间复杂度，
O(n)O(n) 空间复杂度，O(n)O(n) 时间复杂度，
注意事项
你可以假设只有一组答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    /**
     * @param numbers: An array of Integer
     * @param target: target = numbers[index1] + numbers[index2]
     * @return: [index1 + 1, index2 + 1] (index1 < index2)
     */
    vector<int> twoSum(vector<int> &numbers, int target) {
        // write your code here
        int i = 0;
		int j = 0;
		vector<int> a;
		for (i = 0; i < numbers.size(); i++)
		{
			for (j = i + 1; j < numbers.size(); j++)
			{
				if ((numbers[i] + numbers[j]) == target)
				{
					a.push_back(i);
					a.push_back(j);
					return a;
				}
				else
				{
					continue;
				}
			}
		}
    }
};

82.落单的数

给出 2 * n + 1个数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。

样例
样例 1:

输入：[1,1,2,2,3,4,4]
输出：3
解释：
仅3出现一次
样例 2:

输入：[0,0,1]
输出：1
解释：
仅1出现一次
挑战
一次遍历，常数级的额外空间复杂度

注意事项
n≤100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    /**
     * @param A: An integer array
     * @return: An integer
     */
    int singleNumber(vector<int> &A) {
        // write your code here
        int ans = 0;
        for(int i=0; i<A.size(); ++i)
            ans ^= A[i];
        return ans;
    }
};

参与运算的两个值，如果两个相应bit位相同，则结果为0，否则为1。
即：0^0 = 0， 1^0 = 1， 0^1 = 1， 1^1 = 0
按位异或的3个特点:
(1) 0^0=0,0^1=1 0异或任何数＝任何数
(2) 1^0=1,1^1=0 1异或任何数－任何数取反
(3) 任何数异或自己＝把自己置0
思路：通过异或，相同的数结果为0，那么最后的结果一定是落单的数字。