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。
