P08 两数之和(双指针、二分法、BF、map标记法)

傷城~ 2022-10-19 12:51 5阅读 0赞

# 一、无序数组 #

## 1.1 暴力算法 ##

// 无序暴力算法 时间O(n^2), 空间O(1)
    func (s *SumOfTwoNumber) BF(target int) (int, int) { 
    	for i := 0; i < len(s.array); i++ { 
    		for j := i + 1; j < len(s.array); j++ { 
    			if s.array[i]+s.array[j] == target { 
    				return i, j
    			}
    		}
    	}
    	return -1, -1
    }

## 1.2 map标记法 ##

遍历当前值和历史值列表之和是否==target

// 无序类埃塞法 时间O(n), 空间O(n)
    func (s *SumOfTwoNumber) Ethiopian(target int) (int, int) { 
    	eMap := make(map[int]int) // 值、下标
    	for index, item := range s.array { 
    		if val, ok := eMap[target-item]; ok { 
    			return val, index
    		}
    		eMap[item] = index
    	}
    	return -1, -1
    }

# 二、有序数组 #

## 2.1 二分法 ##

// 有序二分法 时间O(NlogN), 空间O(1)
    func (s *SumOfTwoNumber) HalfSearch(target int) (int, int) { 
    	for index, item := range s.OrderedArray { 
    		find := target - item // 需要寻找的值
    		var left, right = 0, len(s.OrderedArray) - 1
    		for left <= right {  // 当左边的值大于右边值即止
    			mid := (left + right) / 2
    			if s.OrderedArray[mid] < find {  // 太小，增大left
    				left = mid + 1
    			} else if s.OrderedArray[mid] > find {  // 太大，减小right
    				right = mid - 1
    			} else { 
    				return index, mid
    			}
    		}
    	}
    	return -1, -1
    }

## 2.2 双指针 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70_pic_center]

// 有序双指针 时间O(N), 空间O(1)
    func (s *SumOfTwoNumber) DoublePoint(target int) (int, int) { 
    	var left, right = 0, len(s.OrderedArray) - 1
    	for left < right { 
    		if s.OrderedArray[left]+s.OrderedArray[right] > target {  // 太大
    			right--
    		} else if s.OrderedArray[left]+s.OrderedArray[right] < target {  // 太小
    			left++
    		} else { 
    			return left, right
    		}
    	}
    	return -1, -1
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/842efc781e1a4452a7412bf058530069.png