1.数组中的问题最常见

排序；选择排序；插入排序；归并排序；快速排序
查找：二分查找
数据结构：栈；队列；堆


对于整型溢出的问题，所以这里 int mid = l + (r-l)/2


2.面试问题实战

2.1简单问题

思路1：扫描数组，将所有不为零的数取出，按照相对位置，赋到数组的开头，数组剩余位置全部补零

2.2滑动窗口思想

滑动窗口是处理字符串和数组的经典方法,时间复杂度O(n)。
滑动窗口在字符串上从左到右滑动,一直到字符串的尾部,滑动窗口的长度是动态变化的,需要两个指针指向窗口的两边,指针i指向窗口的左边界,指针j指向窗口的右边界.

2.2.1给定一个整型数组和一个数字S，找到数组中最短的一个连续子数组，使得连续子数组的数字和sum>=S，返回这个最短连续子数组的长度 

class Solution
{
public:
	int minSubArrayLen(int s, vector<int>& nums) {
		int l = 0;
		int r = -1;// nums[l...r]为我们的滑动窗口
		int sum = 0;
		int res = nums.size() + 1;

		while ( l < nums.size())
		{
			if (r + 1 < nums.size() && sum < s)
			{
				r++;
				sum += nums[r];
			}
			else {
				sum -= nums[l];
				l++;
			}
			if (sum >= s)
				res = __min(res, r - l + 1);
		}
		if (res == nums.size() + 1)
			return 0;
		return res;

	}

};

2.2.2 给定一个字符串，寻找这个字符串中不包含重复字母的最长子串。 

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int freq[256] = { 0 };
		int l = 0, r = -1;
		int res = 0;
		while (l < s.size())
		{
			if (r + 1 < s.size() && freq[s[r + 1]] == 0) 
				freq[s[++r]] ++;

			else{
				freq[s[l++]] --;
			}
			res = max(res, r - l + 1);

		}
		return res;
    }
};

2.3查找问题

一共有两类：1、查找有无此元素---------set容器

2、查找对应关系------------map容器

set和map的常见操作：

insert  set不承载重复元素，即便是insert进去相同的元素，set中也只保存一个元素

find
erase
change(map的操作)

2.3.1给定两个数组，编写一个函数来计算它们的交集。 
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [9,4]
		
		
		
		
		
		

			说明: 
		


		
    
			
			
  • 
				输出结果中的每个元素一定是唯一的。
			

			
  • 
				我们可以不考虑输出结果的顺序。
			

		



class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> record(nums1.begin(),nums1.end());
        set<int> resultSet;
        for(int i = 0; i < nums2.size();i++)
            if(record.find(nums2[i]) != record.end())
                resultSet.insert(nums2[i]);
        vector<int> resultVector(resultSet.begin(),resultSet.end());
        return resultVector;
    }
};

2.3.2给定两个数组，编写一个函数来计算它们的交集

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

说明：

  • 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
  • 我们可以不考虑输出结果的顺序。 
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        map<int,int> resultMap;
        for(int i = 0;i<nums1.size();i++){
            resultMap[nums1[i]] ++;
        }
        vector<int> resultVector;
        for(int i = 0;i < nums2.size();i++){
            if(resultMap[nums2[i]] > 0){
                resultVector.push_back(nums2[i]);
                resultMap[nums2[i]] --;
            }
        }
        return resultVector;
    }
};

set和map的底层实现


但是哈希表失去了数据的顺序性

在C++语言中

2.3.3使用查找表的经典问题

1、给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路：可以排序后使用双指针对撞的思想来进行求解 




 vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> record;
        for(int i = 0;i<nums.size();i++){
            int complement = target - nums[i];
            if(record.find(complement) != record.end()){
                int res[2] = {i,record[complement]};
                return vector<int>(res,res+2);
            }
            record[nums[i]] = i;
        }
        
    }

2、给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
输入: A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2] 输出: 2
时间复杂度为O（n2）,空间复杂度也是O（n2） 
class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        map<int,int> record;
        for(int i = 0;i < A.size();i ++)
            for(int j = 0;j < B.size();j++)
                record[A[i] + B[j]] ++;
        
        int result = 0;
        for(int i = 0;i<C.size();i++){
            for(int j = 0;j < D.size();j++){
                if(record.find(0-C[i]-D[j]) != record.end())
                    result += record[0-C[i]-D[j]];
            }
        }
        return result;
    }
};
对于这个问题，也可以分别将A+B的结果和C+D的结果放到两个查找表中，循环遍历这两个查找表，时间复杂度不变