# hash

## 1. Sum of two numbers

The idea is to save it in the hash table first, and then judge whether it exists again. Use target -

```class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i < nums.length;i++){
if(map.containsKey(target - nums[i])) return new int[]{map.get(target-nums[i]),i};
map.put(nums[i],i);
}
return new int[]{-1,-1};
}
}
```

## 387. The first unique character in a string

The idea is to go through it directly, save the repeated number as false, and then the non repeated number is true. Just return the first one

```class Solution {
public int firstUniqChar(String s) {
Map<Character,Boolean> map = new HashMap<>();
int index = 0;
for(int i = 0;i < s.length();i++){
map.put(s.charAt(i),!map.containsKey(s.charAt(i)));
}
for(int i = 0;i< s.length();i++){
if(map.get(s.charAt(i))) return i;
}
return -1;
}
}
```

The idea is to cycle to judge whether the current node is empty. If it is not empty, start adding value, and then remember to add carry. Divide the current number / 10 for each carry, and then move the three pointers back. Don't forget to take the remainder when adding the data

```class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;

while(l1!=null||l2!=null){
int x = l1 == null? 0:l1.val;
int y = l2 == null? 0:l2.val;

int temp = x + y +carry;
carry = temp / 10;
tail.next = new ListNode(temp % 10);
tail = tail.next;

if(l1!=null) l1 = l1.next;
if(l2!=null) l2 = l2.next;
}

}
}
```

## 19. Delete the penultimate node of the linked list

The most simple and easy to think of writing method is to directly calculate the length first, then reach the position according to the length, and then delete it!

```class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {

cur = cur.next;
}
cur.next = cur.next.next;
}

int getlen(ListNode node) {
int count = 0;
while (node.next != null) {
count++;
node = node.next;
}
return count;
}
}
```

The idea is to form a ring first. Note that you must first define a pointer, then disconnect the ring. Note that the position should take the remainder len-1 (because i + +), and finally disconnect the ring

```class Solution {
public ListNode rotateRight(ListNode head, int k) {

int len = 1;
while(cur.next!=null){
len++;
cur = cur.next;
}
//We must pay attention here
int index = len - k % len -1;
for(int i = 0;i< index;i++){
}

return res;
}
}
```

## 138. Copy linked list with random pointer

The idea is to create a new node, fill the data in the back, and then put a hashtable to get it. As long as it has been saved, it will be retrieved directly

```class Solution {
Map<Node,Node> hashtable = new HashMap<>();

return node;
}
}
```

The iterative algorithm is the head insertion method, and the recursive algorithm is to pay attention to the value of the new node and the stop position

```class Solution {
ListNode pre = null;
ListNode next = null;

while(cur!=null){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}

return pre;
}
}

class Solution {
//The return here is 5, but it stops at 4

return cur;
}
}
```

# Double pointer traversal (sliding window)

The idea is to use two pointers to realize the sliding window, and then the first pointer uses the hash table to reach the place where there is no repetition, and then counts the maximum value each time, and then the next pointer starts to remove characters one by one

## 3. Longest substring without repeated characters

```class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int r = -1,len = s.length(),res = 0;

for(int i = 0;i < len;i++){
if(i != 0){
set.remove(s.charAt(i-1));
}

while(r+1<len && !set.contains(s.charAt(r+1))){
r++;
}

res = Math.max(res,r - i + 1);
}

return res;
}
}
```

## 11. Container with the most water

The idea is to record the area each time, and then take the maximum value, and then move the pointer. The large one does not move, and the small one moves

```class Solution {
public int maxArea(int[] height) {
int l = 0,r = height.length -1,res = 0;
while(l < r ){
int temp = Math.min(height[l],height[r])*(r - l);
res = Math.max(res,temp);
if(height[l]<height[r]){
l++;
}else{
r--;
}
}
return res;
}
}
```

## 26. Delete duplicates in ordered array

The idea is to use the fast and slow pointer. The fast pointer keeps running. If it is wrong, the slow pointer starts running, and then assigned to the slow pointer. Therefore, the index of the slow pointer is actually the length

```class Solution {
//Fast and slow pointer
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length == 0) return 0;

int l = 0,r = 1;
while(r < nums.length){
if(nums[l]!=nums[r]) nums[++l] = nums[r];
r++;
}

return ++l;
}
}
```

## 121. The best time to buy and sell stocks

The idea is to determine the smallest day, and then stop the biggest day. Just count it directly

```class Solution {
//The trick is to determine the minimum value
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE,max = 0;

for(int data : prices){
min = Math.min(min,data);
max = Math.max(max,data-min);
}

return max;
}
}
```

## 209. Minimum length subarray

The idea is similar to that of finding the longest substring without repeated characters, that is, stop every time you get big, let the left pointer move, and then record it yourself

```class Solution {
//It's the same idea as the number of non repeated numbers in the previous statistical array, speed pointer
public int minSubArrayLen(int target, int[] nums) {
if(nums == null || nums.length == 0) return 0;

int l = 0,r = 0,res = 0,min = Integer.MAX_VALUE;

while( r < nums.length){
res += nums[r];
while(target <= res){
min = Math.min(min,r - l + 1);
res -= nums[l];
l++;
}
r++;
}

return min == Integer.MAX_VALUE ? 0 : min;
}
}
```

### Finish work!

Keywords: Java Algorithm leetcode

Added by Jaguar on Mon, 07 Mar 2022 22:14:05 +0200