# leetcode 560. Subarray Sum Equals K

#### 题目

https://leetcode.com/problems/subarray-sum-equals-k/
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Constraints:

The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

#### 源码

class Solution {
public:
unordered_map<int,int> m;
int sum[20005];
int res = 0;
int subarraySum(vector<int>& nums, int k) {
sum[0] = 0;
m[0] = 1;
for(int i = 1;i <= nums.size();++i){
int s = sum[i-1]+nums[i-1];
sum[i] = s;
int re = s-k;
if(m.find(re)!=m.end()){
res+=m[re];
}
if(m.find(s)==m.end()){
m[s]=1;
}else{
m[s]++;
}
}
return res;
}
};


# leetcode28 KMP模板

#### 思路

KMP 模板
https://www.zhihu.com/question/21923021
– 首先理解 PMT，以及根据 PMT 如何进行回溯；其与 next 不同
– next 数组指的是 pattern 当前位匹配不上时，应该回溯到哪一位继续匹配
– p[j] == t[k] 时更新 next[j+1]==k+1，思路时 j+1 匹配不上时回溯要考虑前一位的匹配情况

#### 源码

//
//  leetcode28.cpp
//  test
//
//  Created by sgxm on 2020/8/5.
//

#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>
using namespace std;

vector<int> calNext(string p){
vector<int> next(p.length());
next[0] = -1;
int j = 0,k = -1;
while(j<p.length()-1){
if(k==-1||p[j]==p[k]){
j++;k++;
next[j]=k;
}else{
k = next[k];
}
}
return next;
}
int main(){
string p =      "ababca";
string target = "abcababca";
vector<int> next = calNext(p);
int j = 0,i = 0;
while((j<(int)p.length())&&(i<(int)target.length())){
if(j==-1||p[j]==target[i]){
i++;j++;
}else{
j = next[j];
}
//        if((j<p.length())&&(i<target.length()))
//            cout <<i<<" < "<<target.length()<<","<<j<<" < "<<p.length()<<endl;
}
// cout << j;
if(j == p.length()){
cout <<i-j<<endl;
}else{
cout <<-1<<endl;
}
return 0;
}



# Scala 学习笔记

———— 我自己说的

#### 声明

val 声明必须初始化

import java.lang._ //导入lang中所有
val myStr2：String = HelloWorld!//Scala中的字符串类直接来自于java
println(myStr2)


#### 字面量

val i = 123
val i = true//布尔字面量


#### 操作符

a 方法 b 等价于 a.方法（b）

i += 1

#### 富包装类

Int 对应 RichInt

String 对应 RichString, 这些类位于 scala.runtime 中

#### Range

1 to 5
1.to(5)//1,2,3,4,5
1 until 5//1,2,3,4
0.5f to 5.9f by 0.8f//步长0.8f


#### 输入输出

val str = readLine("enter your name")
>3.5e1
println("hello");println("world!")
printf("i = %.1f",i);//print(),println(),printf()默认所有scala程序都可以使用


#### 写入文件

import java.io.PrintWriter
val out = new PrintWriter("out.txt")
for(i <- 1 to 5) out.println(i)
out.close()


#### 读入文件

import scala.io.Source
val in = Source.fromFile("in.txt")
val lines = in.getLines//返回迭代器
for(line <- lines) println(line)


# 日常学习笔记

## SHA256

50%概率发生哈希碰撞的计算次数

N为哈希值的二进制位数，对于 SHA256 来说，它会生成32字节，64长度的16进制字符串，256位（每个字符取值范围为[0-9a-z]）

n为计算次数，d为取值空间，该公式推导过程中用到了泰勒公式

# 指针和数组

int m;
char n;
int *i;
char *j;
printf("m在内存中占%d个字节\n n在内存中占%d个字节\n",sizeof(m),sizeof(n));
printf("i在内存中占%d个字节\n j在内存中占%d个字节\n",sizeof(i),sizeof(j));
m在内存中占4个字节
n在内存中占1个字节
i在内存中占4个字节
j在内存中占4个字节

//
int a[3] = {1,2,3};
printf("a = %#X\n",a);//a是一个指针常量，指向第一个元素
printf("*a = %d\n",*a);
printf("a[0] = %d\n",a[0]);

//输出
/*
a = 0X69FF04
*a = 1
a[0] = 1
*/

//
int a[3] = {1,2,3};
printf("a[0]的地址为%p\n",&a[0]);
printf("a[1]的地址为%p\n",&a[1]);
printf("a[2]的地址为%p\n",&a[2]);

//输出
/*
a[0]的地址为0069FF04
a[1]的地址为0069FF08
a[2]的地址为0069FF0C
*/

//
int a[3] = {1,2,3};
printf("%p\n",a);
printf("%p\n",a+4);
printf("%p\n",a+1);
printf("%d\n",*(a+1));
/*
0069FF04
0069FF14
0069FF08
2
*/

a+4的结果和a差了16根本不是我们想要的a[1]的地址，而a+1刚好和a相差4，我们输出     a+1指向的变量，刚好也是第二个元素2，这是因为指针变量的加号运算符被重载了它的＋1实际上加的是对应变量的长度，例如字符指针加一就是加一，而整形指针加一就是加四，所以无论是什么类型的数组，a[5]和*（a+5）都是完全等价的

1.（32位）所有类型的指针变量都占4个字节，我们用第一个字节的在内存中的编号来作为它的地址

2. 如果指针p指向i，那么*p完全等价于i

3. 数组在内存中是连续的的，每个元素都是相邻的，是一种连续的线性存储结构

4. a[i]完全等价于*（a + i）

//
using namespace std;
int x[4] = {10,20,30,40};
int *p = x;
cout << *++p << endl;//等价于++p; cout<<*p;
cout << *p++ << endl;//等价于cout<<*p; p++;
cout << ++*p << endl;//等价于int i = *p; ++i; cout<<i;
cout << (*p)++ << endl;
cout << *p << endl;

/*输出
20
20
31
31
32
*/

*++p   *和前自增优先级相同但是结合性是从左到右也就是先执行++在执行*                      *p++   后加加优先级高于*，他会先执行后自增结合的是p，但因为是自增，所以虽然它先执行，但是依然要等到*之后才加一                                                                             ++*p   优先级相同，从右向左，先* 再++  可以和第一个对比