喵，小喵爬天梯系列～美國大公司。
第二彈:整數數組。
1、Remove Element
題意：
給定一個數組和一個值，在原地删除與值相同的數字，傳回新數組的長度。
元素的順序可以改變，并且對新的數組不會有影響。
分析：
小喵的第一想法，竟然題目中用的是vector，直接用用疊代器删除就好了，雖然代碼簡單易寫，但是時間複雜度去可能達到o(n^2)。
那麼我們能不能在o(n)時間解決問題呢？題目要求删除數組中的指定的元素的值x，小喵開始從另一個角度分析問題，就是保留不是指定值x的所有資料，此時就出現的轉機，小喵從k=0，i=0開始掃描，如果不是A[i]！=x就直接替換A[k++] = A[i],這句話對于是x的直接直接覆寫，相等與直接删除。
圖例解釋：
Code1：
int removeElement(vector<int> &A, int elem) {
// write your code here
int n = A.size();
int k = ;
vector<int>::iterator it;
for (it = A.begin(); it != A.end(); ) {
if (elem == (*it)) {
++k;
A.erase(it);
}
else ++it;
}
return n - k;
}
Code2:
int removeElement(vector<int> &A, int elem) {
// write your code here
int n = A.size();
int k = ;
for (int i=;i<n;i++) {
if (elem != A[i]) {
A[k++] = A[i];
}
}
return k;
}
小喵總結：對于這類簡單的題，每一個人都會直接有思路解決，這是我們需要思考一下，是否存在更好的算法，使得時間和空間更少。瞄～
2、Subarray Sum
題意：
給定一個整數數組，找到和為零的子數組。你的代碼應該傳回滿足要求的子數組的起始位置和結束位置。
分析：
記錄1~i的和sum[i]，進行兩層循環的周遊，直接得出答案，時間複雜度o(n^2)。能否o(n)時間解決，假設子數組i+1 ~ j的和為0，則有sum[j] - sum[i] = 0；等式變形sum[i] == sum[j]，我們可以使用hash表記錄，hash[sum[i] ] = i；當到達sum[j]時，hash[sum[j]] = i；則子數組的下标是[i+1, j]。
Code:
class Solution {
public:
/**
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number
* and the index of the last number
* 傳回子數組的和是0的下标的開始和結束（任意一個）。
*/
//if(sum[i] - sum[j] ==0 ) 存在
//sum[j] == sum[i]
//記錄hash[sum[j]] = j
//if 有hash[sum[i]]存在就傳回[hash[sum[i]]+1,,i]
vector<int> subarraySum(vector<int> nums){
vector<int> res;
map<int,int> hash;
hash[] = -;
int sum = ;
for(int i=;i<nums.size();i++){
sum=sum+nums[i];
if(hash.find(sum) != hash.end()){//存在這個值
res.push_back(hash[sum]+);
res.push_back(i);
break;
}
hash[sum] = i;
}
return res;
}
};
小喵總結：還是等式的變換+哈希思想~
3、 Remove Duplicates from Sorted Array
題意：
給定一個排序數組，在原數組中删除重複出現的數字，使得每個元素隻出現一次，并且傳回新的數組的長度。
不要使用額外的數組空間，必須在原地沒有額外空間的條件下完成。
分析：
不要使用額外的數組空間？需要在原數組上進行考慮，充分挖掘所有的有用的資訊，對于排序的數組，我們得到nums[i] == nums[i-1]。原數組上删除，看一下第一個題的雙指針法？用兩個指針i，j，如果nums[i] != nums[i-1]，出現的新的值，就有nums[j] = nums[i];
Code:
class Solution {
public:
/**
* @param A: a list of integers
* @return : return an integer
*/
int removeDuplicates(vector<int> &nums) {
// write your code here
if(nums.size()==) return ;
int i,j;
i=j=;
for(i=;i<nums.size();i++){
if(nums[i]!=nums[i-]){
nums[j++]=nums[i];
}
}
return j;
}
};
小喵總結：雙指針法和哈希思想。
4、Merge Sorted Array
題意：
合并兩個排序的整數數組A和B變成一個新的數組。
你可以假設A具有足夠的空間（A數組的大小大于或等于m+n）去添加B中的元素。
分析:
A有足夠的空間，意味着我們不用開辟新的數組，使用歸并的過程添加到将B數組的指，添加打A數組中即可，從後往前添加，因為我們要在空位置進行指派很安全，避免覆寫A數組中的原來的值，從大到小進行歸并即可。
Code：
class Solution {
public:
/**
* @param A: sorted integer array A which has m elements,
* but size of A is m+n
* @param B: sorted integer array B which has n elements
* @return: void
*/
void mergeSortedArray(int A[], int m, int B[], int n) {
// write your code here
int k=m+n-;
m--; n--;
while(m>=&&n>=){
if(A[m]>=B[n]){
A[k--]=A[m--];
}
else A[k--]=B[n--];
}
while(n>=){
A[k--]=B[n--];
}
}
};
小喵總結：如果面試過程中，沒有明确提示你A的空間很大，你會向面試官詢問嗎？
5、Two Sum
題意：
給一個整數數組，找到兩個數使得他們的和等于一個給定的數 target。
你需要實作的函數twoSum需要傳回這兩個數的下标, 并且第一個下标小于第二個下标。注意這裡下标的範圍是 1 到 n，不是以 0 開頭。
分析：
最簡的方法可以直接用兩層循環進行判斷nums[i] + nums[j] == target,傳回[i,j]。如何降低時間複雜度，一般都是空間換時間，空間？是以想到hash表，分析nums[i] + nums[j] == target；變形得到，nums[j] == target - nums[i]; (這個變形思想在程式設計中很重要)。出現了等式，對于
nums[i],我們紀錄hash[target - nums[i]] = i; 當便利到hash[ nums[j] ] 存在時，一定是hash[nums[j]] = i; 此時有nums[i] + nums[j] == target；傳回[hash[nums[j]]+1, j+1]。
Code：
class Solution {
public:
/*
* @param numbers : An array of Integer
* @param target : target = numbers[index1] + numbers[index2]
* @return : [index1+1, index2+1] (index1 < index2)
* 使用hash紀錄上一個值
*/
vector<int> twoSum(vector<int> &nums, int target) {
// write your code here
map<int, int> hash;
vector<int> res;
for(int i = ;i < nums.size();i ++){
if(hash.find(nums[i]) != hash.end()){//已經存在targe-x = nums[i]
res.push_back(hash[nums[i]] + );
res.push_back(i + );
break;
}
hash[target - nums[i]] = i;
}
return res;
}
};
小喵總結：等式的變形很重要。瞄～
6、 Product of Array Exclude Itself
題意：
給定一個整數數組A。定義B[i] = A[0] * … * A[i-1] * A[i+1] * … * A[n-1]， 計算B的時候請不要使用除法。
分析：
如果可以用除法，就很簡單，紀錄pro = phi _[1-n] A[i] (1-n所有元素的乘積)。B[i] = pro / A[i]。為什麼不能用除法？因為計算機計算時，除法相對乘法慢很多，是以避免懲罰。（面試時就碰到的這個題），那隻能用乘法，對于B[i] = A[0] * … * A[i-1] * A[i-1] * A[i+1] * … * A[n-1]。我們很容易想到周遊所有的i =[0,..n-1]，先計算前一半[0 - i-1]的乘機，再計算後一半[i+1 - n-1]的乘機。注意到，前一半和後一半乘積都是連續的，我們可以提前存下來sum[i]作為0-i的乘積。sum1[i]紀錄n-1 - i的乘積。此時B[i] = sum[i-1] * sum1[i+1];特殊處理一下開頭和結束即可。複雜度O(n)+O(n)。
Code：
class Solution {
public:
/**
* @param A: Given an integers array A
* @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
*/
vector<long long> productExcludeItself(vector<int> &nums) {
// write your code here
vector<long long> A(nums.size(),),B(nums.size(),),res(nums.size(),);
if(nums.size() == ) return res;
A[] = nums[];
for(int i=;i<nums.size();i++){
A[i] = A[i-] * nums[i];
}
B[nums.size()-] = nums[nums.size() - ];
for(int j=nums.size()-;j>=;j--){
B[j] = B[j+] * nums[j];
}
for(int i=;i<nums.size();i++){
if(i==){
res[i] = B[i+];
}
else if(i == nums.size()-){
res[i] = A[i-];
}
else res[i] = A[i-] * B[i+];
}
return res;
}
};
7、First Missing Positive
題意：
給出一個無序的正數數組，找出其中沒有出現的最小正整數。
例如：
如果給出 [1,2,0], return 3
如果給出 [3,4,-1,1], return 2
分析：
很容易想到進行排序之後便利。能否繼續降低時間複雜度？我們排序的時候即使對n個數全部考慮，其實我們隻需考慮1-n之間的數字即可。
例如數組的長度是n，對于數字i（1<= i <=n）。如果存在，那麼在一個排序的數組中，它一定在第i-1個位置。是以，我們周遊所有的數，例如A[i]，如果 1 <= A[i] <=n。它的位置一定在下标A[i] - 1處。是以我們隻需交換到它所在的位置，完成排序，之後周遊一下，如果發現A[i-1] != i。i就是第一個丢失的正整數。
Code：
class Solution {
public:
/**
* @param A: a vector of integers
* @return: an integer
*/
int firstMissingPositive(vector<int> A) {
// write your code here
int len = A.size();
/**
* 我們不用管其他的值，隻需要計算1-n之間的值是否在自己應該在位置即可
* 是以我們可以将任意一個1-n直接的值放到它應該在的位置即可。
* 之後周遊一遍，遇到第一個不在其位置的值就是丢失的值。
*/
for(int i=;i<len;i++){
while(A[i]>&&A[i]<=len&&A[A[i]-]!=A[i]){//第i-1個位置的數不是i,注意while
swap(A[i],A[A[i]-]);
}
}
for(int i=;i<len;i++){
if(A[i]!=i+) return i+;
}
return len+;
}
};
8、3Sum Closest
題意:
給一個包含 n 個整數的數組 S, 找到和與給定整數 target 最接近的三元組，傳回這三個數的和。
分析：
如果是要求兩個數的和最接近目标的值target，可以排序+二分，對于三個數，我們可以排序，然後固定一個值i, 從j = i + 1, r = n-1，進行二分得到結果。時間複雜度從直接暴力的O(n^3)降級到O(n^2)。
Code:
class Solution {
public:
/**
* @param numbers: Give an array numbers of n integer
* @param target: An integer
* @return: return the sum of the three integers, the sum closest target.
* 固定一個值，另外的兩個指針進行二分
*/
int threeSumClosest(vector<int> nums, int target) {
// write your code here
sort(nums.begin(),nums.end());
int ans = nums[] + nums[] + nums[];
for(int i=;i<nums.size();i++){
int l = i+,r = nums.size() - ;
while(l < r){
int sum = nums[i] + nums[l] + nums[r];
if(abs(sum - target) < abs(ans - target)) ans = sum;
if(sum < target) l ++;
else r--;
}
}
return ans;
}
};
9、3Sum
題意：
給出一個有n個整數的數組S，在S中找到三個整數a, b, c，找到所有使得a + b + c = 0的三元組。
分析：
此題和上一題是一樣的題，隻是把target=0，要求得到所有的組合，這裡我們需要注意的是，不要出現同樣的組合。例如[-3,1,1,2]，我們第一個選擇-3，之後二分1+2-3=0。但是接下來還是1和2，又會出現1+2-3=0，是以我們排序後遇到連續相同的值，需要僅僅處理所有相同值的最後一個即可。
Code:
class Solution {
public:
/**
* @param numbers : Give an array numbers of n integer
* @return : Find all unique triplets in the array which gives the sum of zero.
*/
vector<vector<int> > threeSum(vector<int> &nums) {
// write your code here
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int> > result;
for(int i=;i<n-;i++){
if(i!= && nums[i] == nums[i-]) continue; //防止出現相同的組合
int l=i+,r=n-;
int sum = - nums[i];
while(l<r){
if(nums[l] + nums[r] == sum){
vector<int> tmp;
tmp.push_back(nums[i]);
tmp.push_back(nums[l]);
tmp.push_back(nums[r]);
result.push_back(tmp);
l++;
r--;
//防止出現相同的值
while(nums[l-] == nums[l]) l++;
while(nums[r+] == nums[r]) r--;
}
else if(nums[l] + nums[r] < sum) l++;
else r--;
}
}
return result;
}
};
小喵總結：你能不能第一時間想到這些細節問題？
10、Partition Array
題意：
給出一個整數數組 nums 和一個整數 k。劃分數組（即移動數組 nums 中的元素），使得：
所有小于k的元素移到左邊
所有大于等于k的元素移到右邊
傳回數組劃分的位置，即數組中第一個位置 i，滿足 nums[i] 大于等于 k。
分析：
這個題，大家應該都能搞定，就是快排的一次劃分。
Code：
class Solution {
public:
int partitionArray(vector<int> &nums, int k) {
// write your code here
if(nums.size() == ) return ;
int i=,j=nums.size()-;
while(){
//i<=j 注意這一句
while(i<=j && nums[i]<k) ++i;
while(i<=j && nums[j]>=k) --j;
if(i>j) break;
else{
swap(nums[j],nums[i]);
--j; ++i;
}
}
return i;
}
};