Leetcode question brushing (I) -- double pointer (go Implementation)

leetcode Question brushing and sorting series

leetcode Brush problem ( One ) — Two pointer thought
leetcode Brush problem ( Two ) — Sequencing ideas
leetcode Brush problem ( 3、 ... and ) — Dichotomous thinking
leetcode Brush problem ( Four ) — Greedy thoughts

 

leetcode Brush question type （ One ）— Double pointer type

In an ordered array or linked list , The two pointers move left and right （ Dual pointers are divided into dual pointers in the same direction and dual pointers in the opposite direction ）, Find some combinations that meet certain constraints .

Classic title

167 The sum of two numbers of an ordered array

Given a has been according to Non decreasing order Array of integers for numbers , Please find out two numbers from the array, and the sum of them is equal to the target number target .

func twoSum(numbers []int, target int) []int {
    
	i := 0
	j := len(numbers) - 1
	a := make([]int, 2)
	for i < j {
    
		if numbers[i]+numbers[j] == target {
    
			a[0] = i + 1
			a[1] = j + 1
			break
		} else {
    
			if numbers[i]+numbers[j] > target {
      // And greater than the target value , Indicates that the right value should be reduced 
				j--
			} else {
    
				i++
			}
		}
	}
	return a
}

633 Sum of squares

Given a nonnegative integer c , You have to decide if there are two integers a and b, bring a2 + b2 = c .

func judgeSquareSum(c int) bool {
    
	i := 0
	j := (int)(math.Sqrt(float64(c)))  //0^2+j^2=c, therefore j The biggest is c The square root of , Pruning reduces time complexity 
	for i <= j {
    
		m := i*i + j*j
		if m == c {
    
			return true
		} else {
    
			if m < c {
    
				i++
			} else {
    
				j--
			}
		}
	}
	return false
}

345 Reverse vowels in a string

Give you a string s , Invert only all vowels in the string , And return the result string .

func reverseVowels(s string) string {
    
	// Add all vowels to map
	dict := make(map[uint8]int)
	dict['a'] = 1
	dict['e'] = 1
	dict['o'] = 1
	dict['u'] = 1
	dict['i'] = 1
	dict['A'] = 1
	dict['E'] = 1
	dict['O'] = 1
	dict['U'] = 1
	dict['I'] = 1
	// Convert the string to byte Array 
	arr := []byte(s)
	length := len(arr)
	i := 0
	j := length - 1
	for true {
    
		for i < length {
    
			if _, ok := dict[arr[i]]; ok {
      // The left pointer finds the vowel letter 
				break
			}
			i++
		}
		for j > 0 {
    
			if _, ok := dict[arr[j]]; ok {
      // The right pointer finds the vowel letter 
				break
			}
			j--
		}
		if i >= j {
       // After the left and right pointers meet, the exchange ends 
			break
		}
		// Swap left and right pointer vowels 
		tmp := arr[i]
		arr[i] = arr[j]
		arr[j] = tmp
		i++
		j--
	}
	return string(arr)
}

There is also the classic quick sort ~

If there is any wrong , Please point out ~

Reference from ：
http://www.cyc2018.xyz/
https://leetcode-cn.com/problems