2021 - leetcode

525、给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

-(int)findMaxLength:(NSArray *)arr{
    
    int res = 0,sum = 0;
    
    NSMutableArray *numArr = [NSMutableArray array];
    for (int i = 0; i < arr.count; i++) {
        
        if([arr[i] isEqual:[NSNumber numberWithInt:0]]){
            [numArr addObject:@-1];
        }else{
            [numArr addObject:@1];
        }
    }
    
    NSMutableDictionary *dic = [[NSMutableDictionary alloc]init];
    
//    [dic setObject:@"-1" forKey:@"0"];
    
    for (int i = 0; i < numArr.count; i++) {
        
        sum = sum + [numArr[i] intValue];
        
        
        if (![dic.allKeys containsObject:[NSString stringWithFormat:@"%d",sum]]) {
            [dic setObject:[NSString stringWithFormat:@"%d",i] forKey:[NSString stringWithFormat:@"%d",sum]];
        }else{
            
            int t = i - [[dic objectForKey:[NSString stringWithFormat:@"%d",sum]] intValue];
            NSLog(@"两个重复数字质检距离长度->%d",t);
            NSLog(@"res->%d",res);
            
            if (res > (i - [[dic objectForKey:[NSString stringWithFormat:@"%d",sum]] intValue])) {
                
            }else{
                                
                res = i - [[dic objectForKey:[NSString stringWithFormat:@"%d",sum]] intValue];
            }
            
            
        }
        
    }
    
    return res;
    
    
    
}

-(int)findMaxlngth:(NSArray *)arr{
    
    int count = 0;
    int max = 0;
    
    NSMutableDictionary *dic = [[NSMutableDictionary alloc]init];

    for (int i = 0; i<arr.count; i++) {
        
        if ([arr[i] isEqual:[NSNumber numberWithInt:0]]) {
            count++;
        }else{
            count--;
        }
        
        if(![dic.allKeys containsObject:[NSString stringWithFormat:@"%d",count]]){
            [dic setObject:[NSString stringWithFormat:@"%d",i] forKey:[NSString stringWithFormat:@"%d",count]];
        }else{
            
            int temp = [[dic objectForKey:[NSString stringWithFormat:@"%d",count]] intValue];
            
            if (i - temp > max) {
                max = i - temp;
            }
            
            if (count == 0 && max<i+1) {
                max = i+1;
            }
        }
        
    }
    
    return max;
    
    
}

160、相交链表：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

1、哈希表，遍历A链表，将A链表节点存储于哈希表中。
再去遍历B链表，判断是否有重复节点，如果有则返回第一个查到的节点。如果B中所有节点都不在哈希集合中，则两个链表不相交，返回null。

2、双指针，一个指针走到头，然后指向另一个链表头指针，如果有交点就会相遇。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    
    if(!headA || !headB){
        return NULL;
    }

   struct ListNode *p = headA;
   struct ListNode *q = headB;

    while(p != q){
        p = p != NULL ? headA->next : headB;
        q = q != NULL ? headB->next : headA;
    }

    return p;

}

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

1、暴力两边循环
2、两遍哈希，第一
3、单次哈希，通过哈希查找value，没有则根据key，存value。