current position:Home>Algorithm learning -- double pointer

Algorithm learning -- double pointer

2022-01-26 22:25:47 Yan Long

Double pointer classification

  • Speed pointer
  • Left and right pointer

Speed pointer : It mainly solves the problems related to linked lists , such as : A typical way to judge whether a linked list contains a ring 、 The linked list is the second K Nodes, etc Left and right pointer : It mainly solves the problem of array ( Or string ) Problems in : such as : Two points search

Speed pointer

subject : Enter a linked list , Output the last number in the list k Nodes . In order to conform to the habits of most people , From 1 Start counting , That is, the tail node of the list is the last 1 Nodes . for example , A list has 6 Nodes , Start from the beginning , Their values, in turn, are 1、2、3、4、5、6. The last of the list 3 Each node has a value of 4 The node of

ListNode* getKthFromEnd(ListNode* head, int k) {
        

        ListNode* later = head;
        ListNode* first = head;

        for (int i = 0; i < k; i++) {
            if (first == NULL) {
                return NULL;
            }
            first = first->next;
        }

        while(first) {
            later = later->next;
            first = first->next;
        }

        return later;
    }

Left and right pointer

subject : Give a list of... In ascending order Orderly An array of integers nums And an integer target value target, Please find... In the array And is the target value the Two Integers , And return their array subscripts tips: Unordered array summation , have access to map To do it

vector<int> twoSum(vector<int>& nums, int target) {

        vector<int> res;
        
        int left = 0; 
        int right = nums.size() - 1;
        int sum = -1;
        while (left < right) {
            sum = nums[left] + nums[right];
            if (sum == target) {
                res.push_back(left);
                res.push_back(right);
                return res;
            } else if (sum > target) {
                right --;
            } else if (sum < target) {
                left ++;
            }
        }
        return res;
    }

subject : Given an array of integers nums And an integer target value target, Please find... In the array And is the target value the Two Integers , And return their array subscripts

 public int[] twoSum(int[] nums, int target) {

        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int currentFirst = nums[i];
            int needSecond = target - currentFirst;
            int nextIndex = -1;
            if (map.containsKey(needSecond)) {
                nextIndex = map.get(needSecond);
            }
            if (nextIndex >=0) {
                return new int[]{i, nextIndex};
            }
            map.put(currentFirst, i);
        }

        throw new IllegalArgumentException("No two sum solution");
    }

copyright notice
author[Yan Long],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201262225444009.html

Random recommended