本題就是給出一個數k和一個數組，包含N個元素，通過每次添加?數組中的一個數的操作，最后須要得到1 - N的一個序列，不用排序。

能夠從暴力法入手，然后優(yōu)化。

這里利用hash表進行優(yōu)化，終于得到時間效率是O(n*n)的算法，并且常數項應該非常低，速度還挺快的。

思路：

1 假設數組A[i]在1 -N 范圍內，就利用bool B[]記錄，這個數已經找到了；

2 假設A[i]的值之前已經找到了，那么就添加?k操作，得到新的值A[i]+k，看這個值是否找到了，假設沒找到，就使用B記錄，假設之前已經找到了，那么就繼續(xù)反復添加?k的操作。

3 假設最后A[i]+k大于N了，那么就能夠返回IMPOSIBLE了，由于這樣不可能得到要求的數列了。

本算法的缺點是須要額外O(n)的bool空間，只是一般算法會通過sort之后處理也須要O(lgn)的int空間了，所以空間效率事實上也差點兒相同。

而本算法的長處是：不須要排序，不須要做模運算，常數項應該低點，執(zhí)行速度快。

      #include <vector>
#include <string>
using namespace std;

class IncrementingSequence
{
public:
	string canItBeDone(int k, vector<int> &A)
	{
		int N = (int)A.size();
		vector<bool> B(N+1);
		for (int i = 0; i < N; i++)
		{
			if (A[i] > N) return "IMPOSSIBLE";
			while (A[i] <= 0 || B[A[i]])
			{
				A[i] += k;
				if (A[i] > N) return "IMPOSSIBLE";
			}
			B[A[i]] = true;//不要錯寫成B[i]
		}
		for (int i = 1; i <= N; i++)	//別漏這個循環(huán)推斷
		{
			if (!B[i]) return "IMPOSSIBLE";
		}
		return "POSSIBLE";
	}
};
    

附一道250分的水題，須要找a*b +c = y，給出y找到a,b,c當中a, b, c 不能等于0， 或者1

      #include <vector>
#include <math.h>
using namespace std;

class AddMultiply
{
public:
	vector<int> makeExpression(int y)
	{
		vector<int> vx(3);
		vx[0] = -1; vx[1] = 2;
		vx[2] = y - vx[0] * vx[1];
		return vx;
	}
};
    

當然，假設還有額外的限制，那么本算法不是完好的，只是這里不錯的思路是先找好難的部分，乘法部分，然后找加數就easy了。