配列に1回しか現れない数字と、Sの連続正数シーケンスと、Sの2つの数字(剣指offer 40-42)c++バージョン

#include 
#include 
#include 

using namespace std;

class Solution {
     
public:
	//JZ40            
	void FindNumsAppearOnce(vector<int> data, int* num1, int *num2);
	int findfirstof1(vector<int> data);
	bool isindex1(int num, int index);
	//JZ41   S       
	vector<vector<int> > FindContinuousSequence(int sum);
	//JZ42   S     
	vector<int> FindNumbersWithSum(vector<int> array, int sum);//        ,     ，        
};

//JZ40            
void Solution::FindNumsAppearOnce(vector<int> data, int* num1, int *num2) {
     
	if (data.empty())	return;
	*num1 = 0, *num2 = 0;//   ^0     
	int index = findfirstof1(data);
	for (vector<int>::iterator it = data.begin(); it != data.end(); it++) {
     
		// index    1        ，                   
		if (isindex1(*it, index))	*num1 ^= *it;
		else
		{
     
			*num2 ^= *it;
		}
	}
	return;
}
int Solution::findfirstof1(vector<int> data) {
     
	int temp = 0;
	for (vector<int>::iterator it = data.begin(); it != data.end(); it++) {
     
		temp ^= *it;
	}
	int index = 0;
	while (temp) {
     
		if (temp & 1)	return index;
		temp = temp >> 1;
		index++;
	}
	return -1;
}
bool Solution::isindex1(int num, int index) {
     
	if ((num >> index) & 1)	return true;
	return false;
}
//JZ41   S       
vector<vector<int> > Solution::FindContinuousSequence(int sum) {
     
	//      ，            ，             
	//         sum，    ；   ，    。      。
	if (sum <= 2)	return vector<vector<int> >();
	int first = 1, last = 2, mid = sum / 2 + 1;
	int sumtemp = 3;
	vector<vector<int> > result;
	while (first < mid) {
     
		if (sumtemp == sum) {
     
			vector<int> temp;
			for (int i = first; i <= last; i++)
				temp.push_back(i);
			result.push_back(temp);
			sumtemp -= first;
			first++;			
		}
		else if (sumtemp < sum) {
     
			last++;
			sumtemp += last;
		}
		else
		{
     
			sumtemp -= first;
			first++;
		}
	}
	return result;
}
//JZ42   S     
vector<int> Solution::FindNumbersWithSum(vector<int> array, int sum) {
     
	int len = array.size();
	if (len <= 1)	return vector<int>();
	int first = 0, last = len - 1;
	int product = INT_MAX;
	int flag = 0;//            
	vector<int> result(2);
	while (first < len && first < last) {
     
		int sumtemp = array[first] + array[last];
		if (sumtemp == sum) {
     
			flag = 1;
			int producttemp = array[first] * array[last];
			if (producttemp < product) {
     
				result[0] = array[first];
				result[1] = array[last];
				product = producttemp;
			}
			first++;
		}
		else if (sumtemp < sum) {
     
			first++;
		}
		else{
     
			last--;
		}		
	}
	if (flag == 0)	return vector<int>();
	return result;
}

//JZ40            
void test1() {
     
	vector<int> data = {
      1,2,2,3,3,4 };
	int* num1 = new int;
	int* num2 = new int;
	*num1 = 0, *num2 = 0;
	Solution s;
	s.FindNumsAppearOnce(data, num1, num2);
	cout << *num1 << ' ' << *num2;
	delete[] num1;
	delete[] num2;
	return;
}
//JZ41   S       
void test2() {
     
	int sum = 100;
	Solution s;
	vector<vector<int> > result = s.FindContinuousSequence(sum);
	int rows = result.size();
	vector<int>::iterator it;
	for (int i = 0; i < rows; i++) {
     
		for (it = result[i].begin(); it != result[i].end(); it++)
			cout << *it << ' ';
		cout << endl;
	}
	return;
}
//JZ42   S     
void test3() {
     
	vector<int> temp = {
      1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 };
	int sum = 21;
	Solution s;
	vector<int> result = s.FindNumbersWithSum(temp, sum);
	for (vector<int>::iterator it = result.begin(); it != result.end(); it++)
		cout << *it << ' ';
	return;
}


int main() {
     
	//test1();
	//test2();
	test3();
	system("pause");
	return 0;
}

付:JZ 41の正しさを証明する.証明:連続シーケンス{a 0,a 1,...,am}は上記の方法では得られない連続シーケンスであり,{b 0,b 1,...,bl}はbl<=amを満たし、上記の方法で得られた最後の連続シーケンスのセットであるとする.{b 0,b 1,...,bl}の和をsum_と記すb、シーケンスの最初の要素はfirstであり、最後の要素はlastである.

b0 < a0.そうでなければ、b 0=a 0の場合、仮定から分かるように、2つのシーケンスは同じである.b 0>a 0の場合sum_b

上記の方法のルールに従って、このときfirst+,sum_b -= first,sum_b < sum.次はlast++です.case1. sum_b==sum,仮定と矛盾case 2.sum_b < sum, last++. case3. sum_b > sum. first++であり、次にcase 1またはcase 2である.2から分かるように、次に、矛盾するか、case 1またはcase 2である.case 1の前に、lastまたはfirstは{ai}の尾または頭部に等しい(case 1とcase 2が同時に発生することは不可能であるため、両者が同時に到達することは不可能である.1)firstが先頭に到達する場合.この場合、last
注:JZ 42の証明は上記の証明と似ている.