hash表

和为k的子数组

int sum[20020];
//先求前缀和再用hash表遍历
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        
        for(int i=0;i<nums.size();i++){
            sum[i+1] = sum[i]+nums[i];
        }
        unordered_map<int,int> um;
        int res =  0;
        for(int i=0;i<=nums.size();i++){
            if(um.count(sum[i]-k))
                res += um[sum[i]-k];
            um[sum[i]]++;
        }
        return res;
        
    }
};

连续数组

//把所有的0改成-1，然后就和上题一样去找和为1的连续数组，就是先求前缀和在用hash表遍历
int sums[50050];

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        for(int i=0;i<n;i++)
            if(!nums[i])
                nums[i] = -1;
        
        for(int i=0;i<n;i++){
            sums[i+1] = sums[i] + nums[i];
        }
        unordered_map<int,int> um;
        int res = 0;
        for(int i=0;i<=n;i++){
            if(um.count(sums[i])){
                
                res = max(res,i-um[sums[i]]);
            }
            else
                um[sums[i]] = i;
        }
        return res;
    }
};

雪花雪花雪花
算出雪花旋转和翻转的最小表示，然后去这两个最小表示中的最小序列，再将其排序，二维数组的排序可以用一维数组索引替代，之后对比前两个如果相同，那么就说明雪花是相同的

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int s[N][6],idx[N];

bool cmp_min(int a[],int b[]){
    for(int i=0;i<6;i++){
        if(a[i]<b[i]) return true;
        else if(a[i]>b[i]) return false;
    }
    return false;
}

bool cmp(int a,int b){
    return cmp_min(s[a],s[b]);
}

void get_min(int snow[]){
    static int b[12];
    for(int i=0;i<12;i++) b[i] = snow[i%6];
    int i = 0,j = 1,k;
    
    while(i<6&&j<6){
        for(k=0;k<6&&b[i+k]==b[j+k];k++);
        if(b[i+k]>b[j+k]){
            i = i + k+1;
            if(i==j) i++;
        }
        else{
            j = j + k + 1;
            if(i==j) j++;
        }
    }
    int res = min(i,j);
    for(int i = 0;i<6;i++) snow[i] = b[res+ i];
}

int main(){
    int n;
    cin>> n;
    int snow[6],isnow[6];
    for(int i=0;i<n;i++){
        for(int j=0,k=5;j<6,k>=0;j++,k--){
            cin>>snow[j];
            isnow[k] = snow[j];
        }
        
        get_min(snow);
        get_min(isnow);
        
        if(cmp_min(snow,isnow)) memcpy(s[i],snow,sizeof(snow));
        else memcpy(s[i],isnow,sizeof(isnow));
        
        idx[i] = i;
    }
    
    sort(idx,idx+n,cmp);
    
    int flag = 0;
    for(int i=1;i<n;i++){
        if(!cmp_min(s[idx[i]],s[idx[i-1]])&&!cmp_min(s[idx[i-1]],s[idx[i]])){
            flag = 1;
            break;
        }
    }
    if(flag) cout<<"Twin snowflakes found."<<endl;
    else cout<<"No two snowflakes are alike."<<endl;

    return 0;
}

转载于:https://www.jianshu.com/p/c010c7624aba